Mô tả và yêu cầu

Tầng áp mái thường được sử dụng như nhà kho lưu trữ các giấy tờ, đồ đạc cũ
và ít ai lên đó. Hôm nay, Bình có việc lên đó tìm cuốn album lưu ảnh của những thế
hệ trước trong gia đình.
Ô khoá mở cánh cửa có hai vòng tròn xoay hình tròn,vòng xoay thứ nhất đang
chỉ tới số a, vòng xoay thứ hai đang chỉ tới số b. Các vòng xoay chỉ có thể xoay theo
chiều kim đồng hồ. Khi xoay một vòng, số được chỉ sẽ tăng thêm 1. Cánh cửa sẽ mở
khi các số a và b nhận được có ước chung khác 1.
Đáng tiếc, do để lâu không dùng vòng xoay thứ nhất bị kẹt, không xoay được
và vì vậy luôn chỉ tới số a. Như vậy chỉ có thể xoay vòng xoay thứ hai.
Yêu cầu: Hãy xác định số vòng xoay tối thiểu cần thực hiện của vòng xoay thứ
hai để mở cửa.
Dữ liệu: Vào từ thiết bị nhập chuẩn gồm
 Dòng thứ nhất chứa số nguyên n và cặp số a, b (1 ≤ n ≤ 100)
 Dòng thứ i trong n dòng sau chứa 2 số nguyên a và b cách nhau một dấu
cách (2 ≤ a, b ≤ 109).

Kết quả: Ghi ra thiết bị xuất chuẩn, với mỗi test đã cho in ra trên một dòng
một số nguyên là lời giải tìm được.

Ví dụ

INPUT                              OUTPUT
               3                                   2
               15 7                                12
               23 11                               0
               35 42

      Giới hạn:
      Subtask 1: 50% số test tương ứng với n = 1, 1 ≤ a, b ≤105.
      Subtask 2: 30% số test tương ứng với 1 ≤ a, b ≤105.

      Subtask 3: 20% số test còn lại không có ràng buộc gì.