CF1657A.Integer Moves

There's a chip in the point $(0, 0)$ of the coordinate plane. In one operation, you can move the chip from some point $(x_1, y_1)$ to some point $(x_2, y_2)$ if the Euclidean distance between these two points is an integer (i.e. $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ is integer).

Your task is to determine the minimum number of operations required to move the chip from the point $(0, 0)$ to the point $(x, y)$.

坐标平面上的点 $(0, 0)$ 处有一个芯片。在一次操作中，你可以将芯片从某点 $(x_1, y_1)$ 移动到某点 $(x_2, y_2)$，当且仅当这两点之间的欧几里得距离为整数（即 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 为整数）。

你的任务是确定将芯片从点 $(0, 0)$ 移动到点 $(x, y)$ 所需的最少操作次数。

The first line contains a single integer $t$ ($1 \le t \le 3000$) — number of test cases.

The single line of each test case contains two integers $x$ and $y$ ($0 \le x, y \le 50$) — the coordinates of the destination point.

第一行包含一个整数 $t$（$1 \le t \le 3000$）—— 测试用例的数量。

每个测试用例的单行包含两个整数 $x$ 和 $y$（$0 \le x, y \le 50$）—— 目标点的坐标。

For each test case, print one integer — the minimum number of operations required to move the chip from the point $(0, 0)$ to the point $(x, y)$.

对于每个测试用例，输出一个整数——将筹码从点 $(0, 0)$ 移动到点 $(x, y)$ 所需的最少操作次数。

In the first example, one operation $(0, 0) \rightarrow (8, 6)$ is enough. $\sqrt{(0-8)^2+(0-6)^2}=\sqrt{64+36}=\sqrt{100}=10$ is an integer.

In the second example, the chip is already at the destination point.

In the third example, the chip can be moved as follows: $(0, 0) \rightarrow (5, 12) \rightarrow (9, 15)$. $\sqrt{(0-5)^2+(0-12)^2}=\sqrt{25+144}=\sqrt{169}=13$ and $\sqrt{(5-9)^2+(12-15)^2}=\sqrt{16+9}=\sqrt{25}=5$ are integers.

在第一个例子中，只需一次操作 $(0, 0) \rightarrow (8, 6)$ 即可。$\sqrt{(0-8)^2+(0-6)^2}=\sqrt{64+36}=\sqrt{100}=10$ 是整数。

在第二个例子中，棋子已位于目标点。

在第三个例子中，棋子可按如下方式移动：$(0, 0) \rightarrow (5, 12) \rightarrow (9, 15)$。$\sqrt{(0-5)^2+(0-12)^2}=\sqrt{25+144}=\sqrt{169}=13$ 和 $\sqrt{(5-9)^2+(12-15)^2}=\sqrt{16+9}=\sqrt{25}=5$ 均为整数。