Anti Light's Cell Guessing
Contest: Codeforces Global Round 17
Difficulty rating: 900
Tags: math

You are playing a game on a $$$n \times 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, you will choose some $$$k$$$ and some $$$k$$$ cells $$$(x_1, y_1),\, (x_2, y_2), \ldots, (x_k, y_k)$$$, and give them to the computer. In response, you will get $$$k$$$ numbers $$$b_1,\, b_2, \ldots b_k$$$, where $$$b_i$$$ is the manhattan distance from $$$(x_i, y_i)$$$ to the hidden cell $$$(x, y)$$$ (so you know which distance corresponds to which of $$$k$$$ input cells).

After receiving these $$$b_1,\, b_2, \ldots, b_k$$$, 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 $$$(a_1, b_1)$$$ and $$$(a_2, b_2)$$$ is equal to $$$|a_1-a_2|+|b_1-b_2|$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — 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 \le n, m \le 10^9$$$) — the number of rows and the number of columns in the grid.

Output format:
For each test case print a single integer — the minimum $$$k$$$ for that test case.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the smallest such $$$k$$$ is $$$2$$$, for which you can choose, for example, cells $$$(1, 1)$$$ and $$$(2, 1)$$$.

Note that you can't choose cells $$$(1, 1)$$$ and $$$(2, 3)$$$ for $$$k = 2$$$, as both cells $$$(1, 2)$$$ and $$$(2, 1)$$$ would give $$$b_1 = 1, b_2 = 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 = 1$$$, for it you can choose cell $$$(3, 1)$$$ or $$$(1, 1)$$$.

Example input:
2
2 3
3 1

Example output:
2
1

Editorial:
$$$\mathcal Complete\;\mathcal Solution$$$:
$$$\textbf{I encourage you to read the Hints and Assumptions before reading this.}$$$
Let's say the answer is $$$ans$$$. If $$$n == 1$$$ and $$$m == 1$$$, then there's only one cell, so we don't need any more information, and the hidden cell is that single cell. So for this scenario $$$ans = 0$$$.
If exactly one of $$$n$$$ or $$$m$$$ equals $$$1$$$, then it's trivial that the answer is greater than $$$0$$$. Also if we choose the cell $$$(1, 1)$$$, we can find the hidden cell. So for this case $$$ans = 1$$$.
Now assume $$$2 \le n$$$ and $$$2 \le m$$$, if you choose $$$(1, 1)$$$ and $$$(n, 1)$$$ then let's say the distance from $$$(1, 1)$$$ to the hidden cell is $$$b_1$$$ and the distance from $$$(n, 1)$$$ to the hidden cell is $$$b_2$$$. Then if the hidden cell is $$$(i, j)$$$ then $$$b_1 = i-1 + j-1$$$ and $$$b_2 = n-i + j-1$$$ so $$$b_1+b_2 = n-1 + 2j-2$$$ so we can find $$$j$$$. After finding $$$j$$$ we can find $$$i$$$ using $$$b_1 = i-1+j-1$$$. So the answer is at most $$$2$$$.
Now we proof $$$2 \le ans$$$, trivially $$$0 < ans$$$, but why $$$ans \ne 1$$$?. Assume someone chose a cell $$$(i, j)$$$ and they could distinguish all the $$$n \cdot m$$$ possible hidden cells. It's easy to see that at least $$$3$$$ of the $$$4$$$ cells $$$(i, j-1)$$$, $$$(i+1, j)$$$, $$$(i-1, j)$$$ and $$$(i, j+1)$$$ exist in the table, but their distance from $$$(i, j)$$$ is $$$1$$$ for all $$$4$$$ of them, so we can't distinguish them, so $$$ans = 2$$$.
Time complexity: $$$\mathcal{O}(1)$$$