Cho số nguyên \(P\) có dạng như sau:
\(P\) \(=\) \({p_1}^{e_1} . {p_2}^{e_2} .\) ... \(. {p_k}^{e_k}\) , sao cho với \(\forall i, 1 \leq i \leq k\), \(p_i\) là số nguyên tố, \(e_i \geq 1\) và \({p_i}^{e_i} \leq 2.10^5\)

Cho \(T\) truy vấn, mỗi truy vấn gồm hai số \(N, K\) \((K \leq N)\). Với mỗi truy vấn, bạn hãy tính \(\binom{N}{K}\) \(mod\) \(P\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(T, P\) \((T \leq 10^4)\) lần lượt là số lượng truy vấn và số cho trước.
• \(T\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(N, K\).

Output

• Với mỗi truy vấn, in ra một số nguyên là đáp số của truy vấn đó.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, K \leq 10^3\); \(P \leq 10^9\).
• Subtask \(2\) (\(20\%\) số điểm): \(N, K \leq 10^5\); \(P \leq 2.10^5\), \(P\) là số nguyên tố.
• Subtask \(3\) (\(20\%\) số điểm): \(N, K \leq 10^5\); \(P \leq 10^9\).
• Subtask \(4\) (\(30\%\) số điểm): \(N, K \leq 10^9\); \(P \leq 10^9\).

Example

3 8
7 4
6 3
5 2

3
4
2