Elabore una función que dado dos números, halle el máximo común divisor entre ellos. Dicha función deberá ser recursiva.

El programa debe ir divido por funciones y en comentario la especificación formal de cada una.

Input

La entrada consiste en un número t indicando los casos de prueba. Para cada t se encuentran dos números, cada uno separado por un espacio.

Output

Para cada caso de prueba imprimir el mcd entre los números.

Example

Input:
3
8 4
7 5
2 10

Output:
4
1
2