坐标平面的$$$(0, 0)$$$点有一个缺口。在一次操作中,如果 $$$(x_1, y_1)$$$ 某个点 $$$(x_2, y_2)$$$ 之间的欧氏距离是整数(即 $$$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$$ 是整数),则可以将芯片移动到某个点 $$$(x_2, y_2)$$$。
您的任务是确定将芯片从点 $$$(0, 0)$$$ 移动到点 $$$(x, y)$$$ 所需的最少操作次数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3000$$$) — 测试用例的数量。
每个测试用例的单行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$0 \le x, y \le 50$$$) — 目标点的坐标。
输出
对于每个测试用例,打印一个整数 - 将芯片从点 $$$(0, 0)$$$ 移动到点 $$$(x, y)$$$ 所需的最少操作数。
示例
输入 #1
3 8 6 0 0 9 15
输出 #1
1 0 2
注意
在第一个示例中,一个操作 $$$(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$$$ 是整数。