Anti Light’s Cell Guessing solution codeforces

Anti Light’s Cell Guessing solution codeforces

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

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

After receiving these 𝑏1,𝑏2,,𝑏𝑘b1,b2,…,bk, you have to be able to determine the hidden cell. What is the smallest 𝑘k 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 (𝑎1,𝑏1)(a1,b1) and (𝑎2,𝑏2)(a2,b2) is equal to |𝑎1𝑎2|+|𝑏1𝑏2||a1−a2|+|b1−b2|.

Anti Light’s Cell Guessing solution codeforces Input

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

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

Output

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

Example
input

Copy
2
2 3
3 1

Anti Light’s Cell Guessing solution codeforces output

Copy
2
1
Note

In the first test case, the smallest such 𝑘k 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 𝑘=2k=2, as both cells (1,2)(1,2) and (2,1)(2,1) would give 𝑏1=1,𝑏2=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 𝑘=1k=1, for it you can choose cell (3,1)(3,1) or (1,1)(1,1).

Leave a Comment

Your email address will not be published. Required fields are marked *