Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3224.   Birthday Cake
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 2152   Accepted Runs: 936



ZC's birthday is coming, lxh gives a cake of n * m as present for his girlfriend. Now lxh wants to know how many second do you need to divide it to many 1*1 cakes? Every second you can choose a connected part of cake, and cut it into two along a straight line.

Input

In the first line, an integer T is given indicating the number of test case.

For each case, you can get two integers n and m in the line. (n, m ≤ 109)

Output

For each case, output the answer in a line.

Sample Input

2
1 1
2 2

Sample Output

0
3



Source: The 7th UESTC Programming Contest Preliminary
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz