Description

在坐标平面上有一个弹珠在（ 0 , 0 ）点上，在一次操作中，你可以把该弹珠移动到新的点（ x , y ）上（x,y均为整数），前提是两点间的距离是欧氏距离（即√ [ (x1-x2)²+ (y1-y2)²]是整数）
你的任务是找到弹珠从（ 0 ， 0 ）到（ x , y ）的最少操作数

Format

Input

第一行是T组案例( 1 ≤ T ≤ 3000 )
然后是T行，每行有两个整数 x , y ( 0 ≤ x,y ≤ 50 )表示目标坐标

Output

对于每组案例，打印从（ 0 ， 0 ）到（ x , y ）的最少操作次数并换行

Sample 1

Input

3
8 6
0 0
9 15

Output

1
0
2

Limitation

1s, 1024KiB for each test case.

Hint

Source

每日一题