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 2

Sample Output

1

数据范围：

对于100%的数据，1 < = N , M < = 10000000

题目分析

首先我们知道，若x与y互质，则x+y与y也互质，x+2y与y也互质。。。
换到这道题上来说，若一个数x与m!互质，那么x+(m!)也一定与m!互质，(x+m!*****2)也一定与m!互质。。。
由于n!一定是m!的倍数，于是我们每存在到一个x<=m!与m!互质，我们就一定能找到(n!)/(m!)个与m!互质的数
而m!以内与m!互质的数的数量恰好是φ(m!)
于是我们要得到的数恰好就是φ(m!) * (n!)/(m!) %p
其中m!的所有质因数恰好就是m以内所有的质数 于是φ(m!)=(m!)*∏(pi-1)/pi (pi<=m)
于是最后我们的结果就是n!*∏(pi-1)/pi
质数预处理出来，n!预处理出来，pi的逆元预处理出来，∏(pi-1)/pi就可以预处理出来，都是线性的

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int prime[1000010];
bool vis[10000010];
long long sum[10000010];
long long jie[10000010];
long long yuan[10000010];
long long mod;
int t;
void init()
{
    for(int i=2;i<=10000005;i++)
    {
        if(!vis[i]) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=10000005;j++)
        {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
    jie[0]=1;
    for(int i=1;i<=10000005;i++) jie[i]=(jie[i-1]*i)%mod;
    yuan[1]=1;
    for(int i=2;i<=10000005&&i<mod;i++)
        yuan[i]=(mod-mod/i*yuan[mod%i]%mod);
    sum[1]=1;
    for(int i=2;i<=10000005;i++)
        if(vis[i]) sum[i]=sum[i-1];
        else sum[i]=sum[i-1]*(i-1)%mod*yuan[i%mod]%mod;
}
int main()
{
    scanf("%d%lld",&t,&mod);
    init();
    while(t--)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n",(long long)jie[n]*sum[m]%mod);
    }
    return 0;
}