Description
大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对R取模后的答案即可。R是一个质数。
Input
第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n
Output
共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值
Sample Input
1 11
4 2Sample Output
1
数据范围：
对于100%的数据，1 < = N , M < = 10000000
解题报告：
此题求解1～n!中与 m！互质的数的个数
可以转化为求 n!/m!*phi(m!)
即 n!*∏(pi-1)/pi （ pi为小于m的质数）
o(n)求 mod为质数的逆元
令 t＝MOD/i, k=MOD%i
t*i+k=0 (mod MOD)
k=-t*i (mod MOD)
两边同时除i＊k
inv[i]=-t*inv[k]
inv[i]=-MOD/i*inv[MOD%i]
即 inv[i]=(MOD-MOD/i)*inv[MOD%I]
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 10000001
#define LL long long
bool not_prime[M+100];
LL prime[500500], ans[M+100], fac[M+100], inv[M+100];
int n, m, p, T, tot;
void shi(){tot=0;LL i,j;for (i=2; i<=M; i++ ){if( !not_prime[i] )prime[++tot]=i;for (j=1; j<=tot && prime[j]*i<=M; j++ ){not_prime[prime[j]*i]=1;if( i%prime[j]==0 ) break;}}fac[1]=1;for (i=2; i<=M; i++ )fac[i]=(fac[i-1]*i)%p;inv[1]=1;for (i=2; i<=M && i<p ; i++ )inv[i]=(p-p/i)*inv[p%i]%p;ans[1]=1;for (i=2; i<=M; i++ ){if( !not_prime[i] )ans[i]=ans[i-1]*(i-1)%p*inv[i%p]%p;elseans[i]=ans[i-1];}
}
int main(){scanf("%d%d", &T, &p );shi();for ( int i=1; i<=T; i++ ){scanf("%d%d", &n, &m );printf("%d\n", fac[n]*ans[m]%p);}return 0;
}