题目描述

(Recursive Greatest Common Divisor) The greatest common divisor of integers x and y is the largest integer that evenly divides both x and y. Write a recursive function gcd that returns the greatest common divisor of x and y, defined recursively as follows: If y is equal to 0, then gcd(x, y) is x; otherwise, gcd(x, y) is gcd(y, x % y), where % is the modulus operator. [Note: For this algorithm, x must be larger than y.]


输入格式

The input consists of n (0<n<100) lines.
Each line consists of integers x(range from 1 to 500) and y(range from 0 to 499).
x is larger than y.
The last line of input consists of Int(0).


输出格式


样例数据

输入

252 105
5 0
0

输出

21
5

备注


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

题解