Integer Moves

题意翻译

一个点一开始在二维平面的原点，即 $(0,0)$，每一步它可以移动到任意一个与其距离为整数的点。现在，给定两个整数 $x,y$，求最少要多少步才能够从 $(0,0)$ 走到 $(x,y)$。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 3000$。 - $0\leqslant x,y\leqslant 50$。 Translated by Eason_AC

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3
8 6
0 0
9 15

输出样例 #1

1
0
2

说明

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.