Tăng áp mái thường được dùng làm nhà kho lưu trữ giấy tờ, đồ đạc cũ và ít ai lên đó. Hôm nay, Bình muốn lên đó tìm cuốn album lưu ảnh của những thế hệ trước trong gia đình.

Ổ khóa mở cánh cửa có hai núm xoay hình tròn, núm thứ nhất đang chỉ tới số a, núm thứ hai đang chỉ tới số b. Mỗi lần xoay núm thứ hai, số trên núm sẽ tăng thêm 1 (xoay theo chiều kim đồng hồ).

Cánh cửa sẽ mở khi ước chung lớn nhất (UCLN) của a và b khác 1.

Tuy nhiên, núm thứ nhất bị kẹt (không xoay được), chỉ xoay được núm thứ hai.

Yêu cầu:

Xác định số vòng xoay tối thiểu của núm thứ hai (mỗi vòng làm tăng b lên 1) để cánh cửa mở được.

Dữ liệu vào (DOOR.INP):

Dòng đầu: số nguyên n là số lượng test (1 ≤ n ≤ 100)

n dòng tiếp theo: mỗi dòng chứa hai số nguyên a và b (2 ≤ a, b ≤ 10⁹)

Dữ liệu ra (DOOR.OUT):

Ghi ra n dòng, mỗi dòng là số nguyên duy nhất là số vòng xoay tối thiểu cần thực hiện để mở được cửa.

Ví dụ:

DOOR.INP

3
15 7
23 11
35 42

DOOR.OUT

2
12
0

Giải thích:

Test 1: 15 và 7 không có ước chung, thử 7+1=8 ⇒ UCLN(15,8)=1; 7+2=9 ⇒ UCLN(15,9)=3 ⇒ cần 2 vòng.

Test 2: Tăng dần b cho đến khi UCLN(23,b) > 1, cụ thể sau 12 vòng (11+12 = 23) ⇒ UCLN(23,23)=23.

Test 3: 35 và 42 đã có UCLN=7 ⇒ cần 0 vòng.