Vào ngày sinh nhật của Sutol, The Mastermind muốn tặng cô một chiếc dây chuyền ngọc do anh tự làm. Anh ta dự định sẽ làm nó bằng viên ngọc. Mặt khác, anh sở hữu loại ngọc, mỗi loại có vô số viên và có thể biểu thị mỗi loại bởi các con số từ đến . Chiếc dây chuyền không nhất thiết phải có đủ loại, tức là được phép có nhiều viên cùng loại trong viên. The Mastermind tự hỏi là anh ta có thể tạo ra bao nhiêu chiếc dây chuyền khác nhau?
Hai chiếc dây chuyền được coi là giống nhau khi mà xoay đi thì chúng giống nhau. Ví dụ như hai chiếc dây chuyền dưới đây là giống nhau:
Tuy nhiên, nếu lật ngược lại thì vẫn coi là khác nhau. Ví dụ như hai chiếc dây chuyền dưới đây được coi là khác nhau:
Yêu cầu: Hãy xác định xem The Mastermind có thể làm được bao nhiêu chiếc vòng khác nhau.
Dữ liệu vào:
Dòng đầu chứa số nguyên là số test .
dòng tiếp theo, mỗi dòng chứa số nguyên và , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra:
Ghi ra dòng, mỗi dòng một số nguyên là số dư của kết quả tìm được tương ứng với mỗi test khi chia cho .
