Cho bảng lưới có các dòng được đánh số thứ tự từ trên xuống dưới bắt đầu từ 0, các cột được đánh số thứ tự từ trái qua phải bắt đầu từ 0.

Một con rô-bốt đang ở ô ~(0,0)~ bắt đầu di chuyển, một bước di chuyển từ ô ~(x_1,y_1)~ sang ô ~(x_2,y_2 )~ trên bảng lưới được xem là hợp lệ nếu khoảng cách Euclidean là một số nguyên, hay nói cách khác ~\sqrt{ (x_1-x_2 )^2+(y_1-y_2 )^2 }~ là một số nguyên.

Yêu cầu: Hãy cho biết cần ít nhất bao nhiêu bước để rô-bốt di chuyển từ ô ~(0,0)~ đến ô ~(x,y)~ cho trước.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên ~t~ ~(1≤t≤3000)~ cho biết số lương testcase
• ~t~ dòng tiếp theo mỗi dòng ghi hai số nguyên ~x~ và ~y~ ~(0≤x,y≤50)~

Kết quả:

• Với mỗi testcase trong Input hãy đưa ra một số nguyên cho biết số bước di chuyển ít nhất từ ô ~(0,0)~ đến ô ~(x,y)~. Mỗi kết quả ghi trên môt dòng.

Ví dụ:

Input

3
8 6
0 0
9 15 

Output

1
0
2