Kunal is a mathematical geek. Today, he got hold on a rectangle R of size N x M and start playing with it. In a move, he chooses smaller side of his rectangle R say W where W < Z ( Z is the other side of his current rectangle R ) and remove a square of size W x W such that the size of new rectangle becomes W x (Z - W). Note that if at any point of time his rectangle becomes square he cannot make a further move. Kunal is playing well with his rectangle suddenly arpit comes in and asks kunal for a mathematical quest. He asks kunal for the minimum size of his rectangle R ( obviously it will be square otherwise kunal can play further ) that he can achieve performing above moves. Kunal is feeling helpless and craving for help. Can you help him ?
Input
First line of input contains a single integer T denoting the number of test cases. First line of each test case contains 2 space separated integer N and M denoting the size of his rectangle.
Output
For each test case, Print the required answer i.e minimum size of square that kunal can achieve following above moves.
Constraints
- 1 ≤ T ≤ 105
- 1 ≤ N, M ≤ 108
Sample Test 1: During his first move kunal chooses smaller side i.e 7 and new size of rectangle will be 7 x 7. After first move, rectangle becomes square and he cannot make further moves. Therefore, minimum square size achieved is 7.
Sample Test 2: During his first move kunal chooses smaller side i.e 2 and new size of rectangle will be 2 x 1. During his second move kunal chooses smaller side of his current rectangle i.e 1 and new size of rectangle will be 1 x 1. Therefore, minimum square size achieved is 1.
