Romero fue al concurso de programación  IP para distribuir manzanas y naranjas entre los concursantes, en el descanso.  
Tiene $N$ manzanas y $M$ naranjas, las cuales deben ser divididas equitativamente entre los concursantes.

Encuentra el número máximo posible de concursantes tal que:

- Cada concursante reciba la misma cantidad de manzanas.
- Cada concursante reciba la misma cantidad de naranjas.
 

Todas las frutas que tiene Romero deben ser distribuidas, no puede sobrar ninguna.

Por ejemplo:
 $2$ manzanas y $4$ naranjas pueden ser distribuidas equitativamente entre $2$ concursantes, donde cada uno recibe $1$ manzana y $2$ naranjas.
 Sin embargo, $2$ manzanas y $5$ naranjas solo pueden ser distribuidas equitativamente a $1$ concursante.
 

La primera línea contiene un entero $T$, ($1 \leq T \leq 1000$) que indica el número de casos de prueba.
Cada uno de los $T$ casos contiene una línea con dos enteros separados por espacio: $N$ y $M$ ($1 \leq N, M \leq 10^9$) el número de manzanas y de naranjas, respectivamente.

Para cada caso de prueba, imprime en una nueva línea el número máximo de concursantes tal que todos reciban la misma cantidad de manzanas y la misma cantidad de naranjas.