[Sdoi2008]沙拉公主的困惑

大富翁国由于通货膨胀和假钞泛滥，决定推行一项新的货币政策。现有钞票的编号范围为 $1$ 到 $N!$，但政府只发行编号与 $M!$ 互质的钞票。

房地产大户沙拉公主想知道大富翁国现有真钞票的数量。请你计算编号在 $1$ 到 $N!$ 之间且与 $M!$ 互质的整数个数。

由于答案可能很大，你只需输出答案对质数 $R$ 取模后的结果。

输入格式

第一行包含两个整数 $T$ 和 $R$，分别表示测试数据的组数和模数。

接下来 $T$ 行，每行包含两个整数 $N$ 和 $M$，表示一组询问。

输出格式

共输出 $T$ 行。对于每组询问，输出编号在 $1$ 到 $N!$ 之间且与 $M!$ 互质的整数个数对 $R$ 取模后的结果。

样例输入

1 11
4 2

样例输出

1

数据范围

• $R$ 为质数；
• $T\le 10^4$；
• $R\le 10^9+10$；
• $1\le M\le N\le 10^7$。

来源与许可

本题为 SDOI 2008 试题「沙拉公主的困惑」，题面与测试数据整理自 BZOJ。

样例 1

输入

1 11
4 2

输出

1