题目描述

在坐标平面上的点 $(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)$ 所需的最少操作次数。

输入格式

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

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

输出格式

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

说明/提示

在第一个样例中，一次操作 $(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$，都是整数。

由 ChatGPT 4.1 翻译

样例

3
8 6
0 0
9 15

1
0
2