A - Pie problem?

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, JavaScript, ... (details)

Fito está considerando comenzar a trabajar como programador. En su primera entrevista le presentaron el siguiente problema: Dada una secuencia de enteros $a_1, a_2, \ldots, a_n$, la cual es además una permutación de $1\ldots n$, se quieren responder preguntas de la forma: si seleccionamos dos números diferentes $a, b$ de la subsecuencia $a_l,a_{l+1},\ldots,a_r$ $(1 \le l < r \le n)$, cuál es el mayor $\gcd(a,b)$ (máximo común divisor) que podemos obtener. Lamentablemente su solución no fue lo suficientemente eficiente, así que ahora es tu tarea demostrar que el problema es muy fácil en realidad.

Input

La primera línea de la entrada contiene el entero $n$ $(2 \le n \le 100000)$. En la segunda línea aparece la secuencia $a_1,a_2,\ldots,a_n$. La tercera línea contiene la cantidad de preguntas a responder $q$ $(1 \le q \le 100000)$. Siguen $q$ líneas, cada una con dos enteros $l, r$ $(1 \le l < r \le n)$, indicando una pregunta.

Output

Para cada pregunta, imprima una línea con la respuesta.

Sample test(s)

Input
10 8 2 4 9 5 7 10 6 1 3 5 2 10 2 4 6 9 1 4 7 10
Output
5 2 2 4 3