时间限制：1秒　　内存限制：256M

---

【题目描述】

　　大富翁国因为通货膨胀，以及假钞泛滥，政府决定推行一项新的政策：现有钞票编号范围为 1 到 \(N\) 的阶乘，但是，政府只发行编号与 \(M!\) 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。
　　现在请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对 \(R\)(是一个质数) 取模后的答案即可。

【输入格式】

　　第一行为两个整数 \(T\) 和 \(R（R≤10^9+10）\)。\(T\) 表示该组数据中测试数据数目，\(R\) 为模，后面 \(T\) 行，每行一对整数 \(N\) 和 \(M\)。

【输出格式】

　　共 \(T\) 行，对于每一对 \(N\) 和 \(M\)，输出 1 到 \(N!\) 中于 \(M!\) 互质数的数量对 \(R\) 取模后的值。

【输入输出样例】

　Input

1 11
4 2

　Output

1

【数据限制】

　　对于 \(20\%\) 的数据，\(1≤M≤N≤10\)，\(T≤10\)。
　　对于 \(40\%\) 的数据，\(1≤M≤N≤10^4\)。
　　对于 \(80\%\) 的数据，\(1≤M≤N≤10^6\)。
　　对于 \(100\%\) 的数据，\(1≤M≤N≤10^7\)，\(T≤10^4\)。

【来源】

　　Mr.he