题意：此题跟POJ 2409类似，只不过只考虑旋转，不考虑翻转；
    但是需要用到快速幂和欧拉函数的优化求解。
    /*
    旋转：顺时针旋转i格的置换中，循环的个数为gcd（i,n），
    每个循环的长度为n/gcd（i,n）。
    如果枚举旋转的格数i,复杂度显然较高。有没有好方法呢？
    可以不枚举i,反过来枚举L.
    由于L|N,枚举了L,再计算有多少个i使得0<=i<=n-1并且L=gcd（i, n）。
    即gcd（i,n）=n/L.
    不妨设a=n/L=gcd（i, n），
    不妨设i=a*t则当且仅当gcd（L,t）=1时
    Gcd（i,n）=gcd（a*L,a*t）=a.
    因为0<=i<n,所以0<=t<n/a=L.
    所以满足这个条件的t的个数为Euler（L）。
    */
    [cpp] view plaincopyprint
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int maxisp = 50000 + 10;
    const int maxp = 8000 + 10;
    int num,n,MOD;
    int prime[maxp];
    int isprime[maxisp];
    inline void get_prime（）
    {
    num=0;
    for（int i=2;i<=maxisp;i++）
    if（！isprime[i]）
    {
    prime[num++]=i;
    for（int j=1;j*i<=maxisp;j++）
    isprime[i*j]=1;
    }
    }
    inline int euler（int x）
    {
    int res=x;
    for（int i=0;i<num&&prime[i]*prime[i]<=x;i++）
    {
    if（x%prime[i]==0）
    {
    res=res/prime[i]*（prime[i]-1）；
    while（x%prime[i]==0）
    x/=prime[i];
    }
    }
    if（x>1）  res=res/x*（x-1）；
    return res;
    }
    //快速幂模版 此处的int可换成long long
    //（A*B）%MOD
    inline int mul（int a,int b,int mod）
    {
    int res=0;
    a%=mod,b%=mod;
    while（b）
    {
    if（b&1）
    {
    res+=a;
    res%=mod;
    }
    a《=1;
    if（a>=mod）   a%=mod;
    b》=1;
    }
    return res;
    }
    //（A^N）%MOD
    inline int pow_mod（int a,int n,int mod）
    {
    int res=1;
    a%=mod;
    while（n）
    {
    if（n&1） res=mul（res,a,mod）；
    a=mul（a,a,mod）；
    n》=1;
    }
    return res;
    }
    int main（）
    {
    int T;
    get_prime（）；
    scanf（"%d",&T）；
    while（T--）
    {
    scanf（"%d%d",&n,&MOD）；
    int ans=0,i;
    for（i=1;i*i<n;i++）
    {
    if（n%i==0）//有长度为L的循环，就会有长度为n/L的循环。
    ans=（ans+euler（i）%MOD*pow_mod（n,n/i-1,MOD）+euler（n/i）%MOD*pow_mod（n,i-1,MOD））%MOD;
    }
    if（i*i==n）//枚举循环长度l,找出相应的i的个数：gcd（i,n）=n/l.
    ans=（ans+euler（i）*pow_mod（n,i-1,MOD））%MOD;
    printf（"%d\n",ans）；
    }
    return 0;
    }