Cho một dãy số gồm \(n\) phần tử, đếm xem có bao nhiêu cách tạo ra một dãy không giảm gồm \(n\) phần tử sao cho mỗi giá trị trong dãy không vượt quá \(n\).

• \(1 \le a_1 \le a_2 \le ... \le a_n \le n\).

Yêu cầu:

• Đếm số dãy thoả mãn yêu cầu bài toán sau khi chia lấy dư cho số nguyên tố \(p\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) \((1 \le T \le 10)\) là số bộ dữ liệu và số nguyên tố \(p\) \((2 \le p \le 10^5)\).
• Tiếp theo là \(T\) bộ dữ liệu, mỗi bộ dữ liệu bao gồm:
  • Một số nguyên dương \(n\) \((1 \le n \le 10^{12})\).

Output

• Mỗi dòng là câu trả lời cho một bộ dữ liệu tương ứng.

Sample Input

2 103
2
4

Sample Output

3
35

Giải thích

• Trong bộ dữ liệu thứ nhất, với \(n = 2\), ta có các dãy thoả mãn: \([1, 1], [1, 2], [2, 2]\).

Ràng buộc

• \(20\%\) số test tương ứng với \(1 \le n \le 1000\).
• \(20\%\) số test tương ứng với \(1 \le n < p \le 10^5\).
• \(60\%\) số test tiếp theo không ràng buộc gì thêm.