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 ~N~ 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ánh cửa, nhanh chóng tiến vào phòng chứa kho báu.

INPUT

• Dòng ~1~: Gồm số nguyên dương ~N~ là số lượng cánh cửa (~1 \le N \le 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 \le x, y \le 10^9~).

OUTPUT

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.

SAMPLE INPUT

3
10 8
13 11
10 3

SAMPLE OUTPUT

0
2
1

SUBTASKS

• ~30 \%~ số test ứng với ~30 \%~ số điểm có ~N = 1~, ~2 \le x, y \le 10^5~.
• ~30 \%~ số test ứng với ~30 \%~ số điểm có ~N \le 100~, ~2 \le x, y \le 10^5~.
• ~40 \%~ số test ứng với ~40 \%~ số điểm có ~N \le 100~, ~2 \le x, y \le 10^9~.