Вам дано масив цілих невід'ємних чисел довжини $n$ і $m$ запитів. Кожен запит~--- два числа $l$ та $r$. Для кожного запиту знайдіть максимум по попарних найбільших спільних дільниках підмасиву від $l$ до $r$, тобто: $$\smash{\displaystyle\max_{l \leq i < j \leq r}} \gcd(a_i, a_j)$$ \InputFile Перший рядок містить одне ціле число $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$)~--- межі запиту. \OutputFile Для кожного запиту виведіть одне ціле число~--- відповідь на нього. \Note $\gcd(a, b)$ ~--- найбільший спільний дільник чисел $a, b$. Розглянемо другий приклад: \begin{itemize} \item У перших чотирьох запитах відрізок складається лише з двох чисел, отже відповідь~--- їхній найбільший спільний дільник. \item Запит $(1, 5)$: найбільший спільний дільник має числа $a_1$ та $a_4$, $\gcd(a_1, a_4)=\gcd(10, 50)=10$. \item Запит $(3, 5)$: потрібно порахувати $\max(\gcd(a_3, a_4), \gcd(a_3, a_5), \gcd(a_4, a_5))=\max(2, 3, 1) = 3$. \item Запит $(1, 3)$: потрібно порахувати $\max(\gcd(a_1, a_2), \gcd(a_1, a_3), \gcd(a_2, a_3))=\max(1, 2, 3) = 3$. \end{itemize} \Scoring \begin{enumerate} \item ($12$ балів): $m, n, a_i \leq 200$; \item ($7$ балів): $m, n \leq 200$; \item ($17$ балів): $a_i \leq 50$; \item ($7$ балів): всі $a_i$~--- степені двійок; \item ($27$ балів): $m, n \leq 15000$; \item ($13$ балів): $m, n \leq 35000$; \item ($17$ балів): без додаткових обмежень. \end{enumerate}