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

第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n

共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <bitset>

 using namespace std;

 const int N=;

 int cnt,prime[N/];

 int a1[N+],a2[N+],inv[N+];

 bool check[N+];

 void Shaker(){

     for(int i=;i<=N;i++){

         if(!check[i])

             prime[++cnt]=i;

         for(int j=;j<=cnt;j++){

             if(i*prime[j]>N)break;

             check[i*prime[j]]=true;

             if(i%prime[j]==)break;

         }

     }

 }

 int main(){

     int T,R,n,m;

     scanf("%d%d",&T,&R);

     Shaker();

     inv[]=;

     for(int i=;i<=N&&i<R;i++)

         inv[i]=1ll*(R-R/i)*inv[R%i]%R;

     a1[]=;

     for(int i=;i<=N;i++)

         a1[i]=1ll*a1[i-]*i%R;

     a2[]=;

     for(int i=;i<=N;i++)

         if(check[i])a2[i]=a2[i-];

         else a2[i]=1ll*a2[i-]*(i-)%R*inv[i%R]%R;

     while(T--){

         scanf("%d%d",&n,&m);

         printf("%d\n",1ll*a1[n]*a2[m]%R);

     }

     return ;

 }