Como es de conocimiento general el máximo común divisor de dos números es: $MCD(n, m) = d$, tal que dicho número es el más grande y divide tanto a $n$ como a $m$.

Osvaldo recientemente aprendió a encontrar el $MCD$ de los números, pero su maestro le dio una tarea más dificíl, en esta tarea Osvaldo debe encontrar  el MCD entre dos números $a$ y $b$, formalmente es: $a \leq MCD(n, m) \leq b$.

Como Osvaldo compró boletos para ir al cine con sus amigos, él desea llegar a tiempo para ver la película, por tal motivo él te pide que le ayudes con este problema.

Se le darán los dos enteros $n$ y $m$, luego $q$ consultas. Cada consulta es un rango de menor a mayor y debe responder cada una de ellas.

La primera línea contiene dos enteros $n$ y $m$, los dos números descritos anteriormente, $(1 \leq n, m \leq 10 ^ 9)$.

La segunda linea contiene un número entero $q$, el número de consultas $(1 \leq q \leq 10 ^ 4)$.

Luego siguen $q$ lineas, cada linea contiene dos números enteros $a$ y $b (1 \leq a, b \leq 10 ^ 9)$.

Imprime $q$ líneas. La i-ésima linea debe contener la respuesta de la i-ésima  consulta, si no existe el $MCD$ en el rango dado debe imprimir $-1$ como resultado de la consulta  correspondiente.