Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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.

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.