# 2829. The Very Greatest Common Divisor

You need to find greatest common divisor of two integers a and b. Each number a and b are determinants of the square matrix of the form:

### 输入格式

The first line of the input file contains number n < 250 of test cases. The description of a test case consists of two lines. The first line contains integer a (0 < a < 1012540), the second – integer b (0 < b < 1012540).

### 输出格式

For each test case print the greatest common divisor of integers a and b on a separate line.

### 样例

Input
3
2
3
3
21
6765
610

Output
1
3
5


2 人解决，7 人已尝试。

3 份提交通过，共有 48 份提交。

9.6 EMB 奖励。