You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

输入格式

第一行为两个整数 $T$ 和 $R$，其中 $T$ 为该组中测试数据数目，$R$ 为模数。

接下来 $T$ 行，每行一对整数 $N$ 和 $M$，具体意义见题目描述。

输出格式

共 $T$ 行，对于每一对 $N$ 和 $M$，输出 $[1, N!]$ 中与 $M!$ 互质的数的数量对 $R$ 取模后的值。

1 11
4 2

1

提示

对于 $100\%$ 的数据，$1\leq M\leq N\leq 10^7$，$1\leq T\leq 10^4$，$2\leq R\leq 10^9+10$ 且 $R$ 为质数。