大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为 $1$ 到 $N$ 的阶乘，但是，政府只发行编号与 $M!$ 互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对 $R$ 取模后的答案即可。$R$ 是一个质数。
第一行为两个整数 $T$，$R$。$R \le 10^9+10$，$T \le 10000$，表示该组中测试数据数目，$R$ 为模
后面 $T$ 行，每行一对整数 $N$，$M$，见题目描述。$M \le N$
共 $T$ 行，对于每一对 $N$，$M$，输出 $1$ 至 $N!$ 中与 $M!$ 互质的数的数量对 $R$ 取模后的值。
1 11 4 2
1
数据范围：
对于 $100\%$ 的数据，$1 \le N , M \le 10000000$
Comet OJ