Mở cửa

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 cầ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. Các núm 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 núm 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 núm thứ hai. Hãy xác định số vòng xoay tối thiểu cần thực hiện của núm thứ hai để mở cửa.

Dữ liệu:

vào từ file DOOR.INP gồm 2 dòng:

• Dòng thứ nhất chứa số nguyên n là số cặp a, b ~(1 \le n \le 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\le a,b \le 10^{9})~.

Kết quả:

ghi ra file DOOR.OUT: Với mỗi test đã cho đưa ra trên một dòng một sô nguyên là lời giải tìm được.

Ví dụ:

DOOR.INP

3

15 7

23 11

35 42

DOOR.OUT

2

12

0

Giới hạn:

• Subtask 1: 50% số test tương ứng với ~n=1, 1\le a, b \le10^{5}~.

• Subtask2: 30% số test tiếp theo tương ứng với ~1 \le a, b \le 10^{5}~.

• Subtask3: 20% so test còn lại không có ràng buộc gì.