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.

Dữ liệu vào:

- 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ả:

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.

Ví dụ:

Ràng buộc:

- Có khoảng 30% số test tương ứng với 30% số điểm với \(n\ = 1,\ 2\ \leq \ x,\ y\ \leq \ 10^{5}\)

- Có khoảng 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ó khoảng 40% số test tương ứng với 40% số điểm với \(n \leq \ 100,\ 2 \leq x,\ y \leq 10^{9}\)