Background

Original link: https://oier.team/problems/X1A。

Problem Description

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)$.

Input Format

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$.

Output Format

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.

3
8 7
999999 1000000
3 3

2
2
3

Hint

Sample Explanation

For the first test case, the robot can move as follows:

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.

For all data ($100\%$): $1\leq T\leq10^5$, $2\leq n,m\leq10^9$.

Translated by ChatGPT 5