Migrated from Lutece 48 Cake

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

ZC's birthday is comming, lxh gives a cake of $n\times m$ as present for his girlfriend.Now lxh wants to know how many second do you need to divide it to many $1\times 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 indects the number of test case.

For each case, you can get two interger $n$ and $m$ in the line. ($n,m \leq 10^9$)

Output

For each case, output the answer in a line.

Samples

2
1 1
2 2

0
3

Resources

电子科技大学第七届ACM程序设计大赛 初赛