How Many Kids Are in the Circle?

A group of kids are standing in a circle and playing catch the ball. For fair play, they always maintain equal distance from one another. Now if the Nth kid is standing right opposite to the Mth kid, how many kids are there in the circle?

Input

The first line of the input contains a single integer T (1 ≤ T ≤ 20), denoting the number of test cases. Then T test cases follows.

Each test case contains two integers N and M (1 ≤ N < M ≤ 109) respectively.

Output

Output a single line for each test case, the number of kids in the circle.

Sample

3
1 3
2 5
4 11

4
6
14