PC3 - MCD

no tags 

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

Added by:Fabio Avellaneda
Date:2009-09-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C++ 4.3.2 CPP HASK