Em cùng nhóm bạn đang tham gia cuộc thi lập trình cho Robot. Nhiệm vụ lần này của robot là nhanh chóng mở được cánh cửa bí mật để tiến vào phòng chứa kho báu. Trên mỗi cánh cửa có in một số nguyên dương \(x\) và một nút nhấn có màn hình đang hiển thị một số nguyên dương \(y\); mỗi lần nhấn nút thì số \(y\) hiển thị trên màn hình sẽ tăng lên \(1\).Cánh cửa sẽ mở khóa nếu ước chung của \(x\) và \(y\) lớn hơn \(1\).

Yêu cầu

Em hãy lập trình cho robot tìm ra số lần nhấn nút ít nhất để mở từng cách cửa, nhanh chóng tiến vào phòng chứa kho báu.

Dữ liệu vào

Cho trong file văn bản ROBOT.INP, có cấu trúc như sau:

• Dòng \(1\): Chứa số nguyên \(N\) là số lượng cánh cửa\((1 \leq N \leq 100)\)
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo: Mỗi dòng chứa hai số nguyên \(x\) và \(y\) cách nhau một dấu cách\((2 \leq x,y \leq 10^9)\).

Kết quả

Ghi ra file văn bản ROBOT.OUT, có cấu trúc như sau:
Với mỗi cặp số \(x\) và \(y\) trong dữ liệu vào, ghi ra một số nguyên là số lần nhấn nút ít nhất tương ứng. Mỗi số ghi trên một dòng riêng biệt.

3
10 8
13 11
10 3

0 
2
1

Ràng buộc

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm với \(N=1, 2 \leq x,y \leq 10^5\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm với \(N \leq 100, 2 \leq x,y \leq 10^5\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm với \(N \leq 100, 2 \leq x,y \leq 10^9\).