Integer Moves codeforces solution in c++

 A. Integer Moves

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There's a chip in the point (0,0)$(0,0)$ of the coordinate plane. In one operation, you can move the chip from some point (x1,y1)$(x_1,y_1)$ to some point (x2,y2)$(x_2,y_2)$ if the Euclidean distance between these two points is an integer (i.e. (x1−x2)2+(y1−y2)2−−−−−−−−−−−−−−−−−−√$\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)$(0,0)$ to the point (x,y)$(x,y)$.

Input

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

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

Output

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

Example

input

Copy

3
8 6
0 0
9 15

output

Copy

1
0
2

Note

In the first example, one operation (0,0)→(8,6)$(0,0)\to (8,6)$ is enough. (0−8)2+(0−6)2−−−−−−−−−−−−−−−√=64+36−−−−−−√=100−−−√=10$\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)→(5,12)→(9,15)$(0,0)\to (5,12)\to (9,15)$. (0−5)2+(0−12)2−−−−−−−−−−−−−−−−√=25+144−−−−−−−√=169−−−√=13$\sqrt{(0-5{)}^2+(0-12{)}^2}=\sqrt{25+144}=\sqrt{169}=13$ and (5−9)2+(12−15)2−−−−−−−−−−−−−−−−−√=16+9−−−−−√=25−−√=5$\sqrt{(5-9{)}^2+(12-15{)}^2}=\sqrt{16+9}=\sqrt{25}=5$ are integers.

solution

#include<iostream>
#include<cmath>
using namespace std;

void solve()
{
	int x, y;
	double ans;
	cin >> x >> y;
	ans = sqrt(pow(0 - x, 2) + pow(0 - y, 2));
	if (x == 0 && y == 0)
		cout << 0 << "\n";
	else if (ans == (int)ans)
		cout << 1 << "\n";
	else
		cout << 2 << "\n";
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}