НСД запросы

Вам дан массив целых неотрицательных чисел длины $n$ и $m$ запросов. Каждый запрос состоит из двух чисел $l$ и $r$. Для каждого запроса необходимо найти максимум среди попарных наибольших общих делителей подмассива от $l$ до $r$, то есть:

Входные данные

Первая строка содержит одно целое число $n$ ($2\le n\le 2\cdot 10^5$) — размер массива.

Вторая строка содержит $n$ целых чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^6$) — элементы массива.

Третья строка содержит одно целое число $m$ ($1\le m\le 2\cdot 10^5$) — количество запросов.

$i$-ая из следующих $m$ строк содержит два целых числа $l_i$, $r_i$ ($1\le l_i<r_i\le n$) — границы запроса.

Выходные данные

Для каждого запроса выведите одно целое число — ответ на него.

Примеры

Примечание

$\gcd (a,b)$ — наибольший общий делитель чисел $a$ и $b$.

Рассмотрим второй пример:

• В первых четырех запросах отрезок состоит только из двух чисел, следовательно, ответ — их наибольший общий делитель.

• Запрос $(1,5)$: наибольший общий делитель имеют числа $a_1$ и $a_4$, $\gcd (a_1,a_4)=\gcd (10,50)=10$.

• Запрос $(3,5)$: нужно посчитать $\max (\gcd (a_3,a_4),\gcd (a_3,a_5),\gcd (a_4,a_5))=\max (2,3,1)=3$.

• Запрос $(1,3)$: нужно посчитать $\max (\gcd (a_1,a_2),\gcd (a_1,a_3),\gcd (a_2,a_3))=\max (1,2,3)=3$.

Оценивание

1. ($12$ баллов): $m,n,a_i\le 200$;

2. ($7$ баллов): $m,n\le 200$;

3. ($17$ баллов): $a_i\le 50$;

4. ($7$ баллов): все $a_i$ — степени двойки;

5. ($27$ баллов): $m,n\le 15000$;

6. ($13$ баллов): $m,n\le 35000$;

7. ($17$ баллов): без дополнительных ограничений.