505009 - 假钞困惑

【题目描述】假钞困惑（question）

因为假钞泛滥，W国政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。试计算现在所有真钞票的数量。 由于可能张数非常大，你只需计算出对一个质数R取模后的答案即可。

输入第一行为两个整数T，R（R≤10^9＋10，T≤10000），其中T表示该组中测试数据数目，R为模。后面T行，每行一对整数N，M（M≤N，1≤N，M≤10000000）。

输出共T行，对于每一对N，M，输出1至N！中与M！互质的数的数量，该数需对质数R取模。