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\).

Dữ liệu vào

• 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\).

Kết quả

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

Ràng buộc

• \(30\%\) số test đầu tiên tương ứng với \(30\%\) số điểm có \(N, K \leq 10^3\); \(P \leq 10^9\).
• \(20\%\) số test tiếp theo tương ứng với \(20\%\) số điểm có \(N, K \leq 10^5\); \(P \leq 2.10^5\), \(P\) là số nguyên tố.
• \(20\%\) số test tiếp theo tương ứng với \(20\%\) số điểm có \(N, K \leq 10^5\); \(P \leq 10^9\).
• \(30\%\) số test tiếp theo tương ứng với \(30\%\) số điểm có \(N, K \leq 10^9\); \(P \leq 10^9\).

Ví dụ

Input

3 8
7 4
6 3
5 2

Output

3
4
2

Chú thích: \(\binom{N}{K}\) là tổ hợp chập \(K\) của \(N\).