Contents

• # For Solution

You are playing a game on a n×mn×m grid, in which the computer has selected some cell (x,y)(x,y) of the grid, and you have to determine which one.

To do so, you will choose some kk and some kk cells (x1,y1),(x2,y2),,(xk,yk)(x1,y1),(x2,y2),…,(xk,yk), and give them to the computer. In response, you will get kk numbers b1,b2,bkb1,b2,…bk, where bibi is the manhattan distance from (xi,yi)(xi,yi) to the hidden cell (x,y)(x,y) (so you know which distance corresponds to which of kk input cells). Anti Light’s Cell Guessing solution codeforces

After receiving these b1,b2,,bkb1,b2,…,bk, you have to be able to determine the hidden cell. What is the smallest kk for which is it possible to always guess the hidden cell correctly, no matter what cell computer chooses?

As a reminder, the manhattan distance between cells (a1,b1)(a1,b1) and (a2,b2)(a2,b2) is equal to |a1a2|+|b1b2||a1−a2|+|b1−b2|.

Input

The first line of the input contains a single integer tt (1t1041≤t≤104) — the number of test cases. The description of test cases follows.

The single line of each test case contains two integers nn and mm (1n,m1091≤n,m≤109) — the number of rows and the number of columns in the grid.

Anti Light’s Cell Guessing solution codeforces Output

For each test case print a single integer — the minimum kk for that test case.

Example

input

Copy
2
2 3
3 1


output Anti Light’s Cell Guessing solution codeforces

Copy
2
1

Note Anti Light’s Cell Guessing solution codeforces

In the first test case, the smallest such kk is 22, for which you can choose, for example, cells (1,1)(1,1) and (2,1)(2,1).

Note that you can’t choose cells (1,1)(1,1) and (2,3)(2,3) for k=2k=2, as both cells (1,2)(1,2) and (2,1)(2,1) would give b1=1,b2=2b1=1,b2=2, so we wouldn’t be able to determine which cell is hidden if computer selects one of those.

In the second test case, you should choose k=1k=1, for it you can choose cell (3,1)(3,1) or (1,1)(1,1).