#1349. ANALYSE - Phân tích số

Cho số nguyên dương . Hãy đếm số cách phân tích thành tổng các số nguyên dương sao cho ước chung lớn nhất của các số này là .

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương là số lượng bộ dữ liệu;
• dòng tiếp theo, mỗi dòng chứa một số nguyên mô tả bộ dữ liệu tương ứng.

Dữ liệu ra:

• Ghi ra dòng, mỗi dòng một số nguyên là kết quả tìm được. Vì con số này có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho .

Ví dụ:

Dữ liệu vào:

2
1
4

Dữ liệu ra:

1
6

Giải thích:

• Trường hợp thứ nhất chỉ có bộ thỏa mãn;
• Trường hợp thứ hai có bộ .

Giới hạn:

• Subtask số điểm của bài có ;
• Subtask số điểm còn lại của bài có .