НСД запити

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

Input

Перший рядок містить одне ціле число $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$) — межі запиту.

Output

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

Examples

Note

$\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$.

Scoring

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$ балів): без додаткових обмежень.