P10713 [MX-X1-T1] "KDOI-05" Simple Infinite Grid Problem

Original link: 。

X is taking part in the KDOI Robot Championship. The arena is an **infinite** grid. X's robot starts at $(1,1)$. He needs to perform several operations to move the robot to $(n,m)$ ($n,m\ge 2$). In the $i$-th operation, X may choose one of four directions: up, down, left, or right, and choose a positive integer $x_i$, then make the robot move $x_i$ steps in that direction. Unfortunately, X's robot has some bugs, so his operations must satisfy the following restriction, otherwise the robot will explode immediately: + For the $i$-th operation, if $i$ is odd, then $x_i$ is also odd; if $i$ is even, then $x_i$ is also even. Please help X compute the minimum number of operations needed to make his robot reach $(n,m)$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. For each test case, the input contains one line with two positive integers $n,m$.

For each test case, output one integer per line, representing the answer. It can be proven that X's robot can always reach $(n,m)$ in a finite number of steps.

**Sample Explanation** For the first test case, the robot can move as follows: $$(1,1)\to(8,1)\to(8,7)$$ A total of $2$ operations are needed. It can be proven that there is no better sequence of operations. **Constraints** **This problem uses bundled testdata.** | Subtask ID | Score | $n,m\leq$ | Special Property | |:--:|:--:|:--:|:--:| | $1$ | $30$ | $10$ | None | | $2$ | $30$ | $10^9$ | $n,m$ have the same parity | | $3$ | $40$ | $10^9$ | None | For all data ($100\%$): $1\leq T\leq10^5$, $2\leq n,m\leq10^9$. Translated by ChatGPT 5