Description:
This is an interactive problem.
You are given a grid with $$$n$$$ rows and $$$m$$$ columns. The coordinates $$$(x, y)$$$ represent the cell on the grid, where $$$x$$$ ($$$1 \leq x \leq n$$$) is the row number counting from the top and $$$y$$$ ($$$1 \leq y \leq m$$$) is the column number counting from the left. It is guaranteed that there are exactly $$$2$$$ mines in the grid at distinct cells, denoted as $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$. You are allowed to make no more than $$$4$$$ queries to the interactor, and after these queries, you need to provide the location of one of the mines.
In each query, you can choose any grid cell $$$(x, y)$$$, and in return, you will receive the minimum Manhattan distance from both the mines to the chosen cell, i.e., you will receive the value $$$\min(|x-x_1|+|y-y_1|, |x-x_2|+|y-y_2|)$$$.
Your task is to determine the location of one of the mines after making the queries.
Input Format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^{3}$$$) — the number of test cases.
The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^{8}$$$, $$$2 \leq m \leq 10^{8}$$$) — the number of rows and columns.
Output Format:
None
Note:
In the first test case, we start by querying the upper-left corner $$$(1, 1)$$$ and get the result $$$3$$$, which means that there is a mine on the counter diagonal, and there is no mine above it.
In the image below, each cell contains a number indicating the distance to the blue cell. The green cells are candidates to contain the nearest mine.
Then we ask three cells on that diagonal, and at the last query, we get the result $$$0$$$, which means that a mine is found at the position $$$(2, 3)$$$.
The second mine was located at the position $$$(3, 2)$$$.
In the second test case, we start by asking the lower-right corner $$$(5, 5)$$$, and get the result $$$1$$$, which means that one of the two neighbours contains a mine, let's call it mine $$$1$$$.
Then we ask cell $$$(2, 2)$$$. We can see that these green cells don't intersect with the green cells from the first query, so they contain the other mine, let's call it mine $$$2$$$.
Query $$$3$$$ is cell $$$(3, 3)$$$. These cells contain mine $$$1$$$, but we still don't know where exactly. Nevertheless, we can determine that the only possible cell for mine $$$2$$$ is $$$(1, 1)$$$, because all other candidates are at a distance closer than $$$3$$$ for this query.