НСД запити

Вхідні дані

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

Другий рядок містить $n$ цілих чисел a_1, a_2, \ldots, 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 \leq 200;

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

3. ($17$ балів): a_i \leq 50;

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

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

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

7. ($17$ балів): без додаткових обмежень.