#825. BIRTHDAY - Sinh nhật

Hôm nay là sinh nhật của giáo sư X. Để đón sinh nhật mình, giáo sư X muốn mua bánh để mời các em học sinh trong trại hè Thái Nguyên. Giáo sư không muốn em học sinh nào phải buồn, vì vậy mỗi em trong đội tuyển sẽ được chia ít nhất một chiếc bánh.

Giáo sư X đã mua chiếc bánh để chuẩn bị cho em học sinh trong trại hè, em học sinh thứ sẽ được chia chiếc bánh. Mặt khác, giáo sư X không thích sự nhàm chán, vì vậy ông ấy muốn chia bánh sao cho không tồn tại số nguyên nào sao cho là ước của tất cả .

Bạn hãy giúp giáo sư X đếm số lượng cách chia bánh khác nhau thỏa mãn điều kiện bài toán. Hai cách chia bánh được coi là khác nhau nếu tồn tại một học sinh nào đó nhận được số bánh khác nhau trong hai cách chia.

Để tăng độ khó của bài toán này, bạn cần giải quyết truy vấn, mỗi truy vấn gồm hai số nguyên dương là và .

Vì kết quả bài toán có thể rất lớn, bạn chỉ cần tìm kết quả bài toán theo modulo

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên dương là số lượng truy vấn;
• dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và lần lượt là số lượng bánh giáo sư X chuẩn bị và số học sinh trong trại hè .

Dữ liệu ra:

• In ra trên dòng kết quả của truy vấn theo modulo .

Giới hạn:

• Subtask và ;
• Subtask và ;
• Subtask là số nguyên tố;
• Subtask Không có ràng buộc gì thêm.

Ví dụ

Dữ liệu vào:

3
5 3
4 2
6 4

Dữ liệu ra:

6
2
10