部分模板（持续更新）

/*--------------------------

           ST表
    求区间最小值（最大值）

--------------------------*/


void RMQ_init(int A[],int d[][])
{
    int n=A.size();
    for (int i=0;iMn;i++) d[i][0]=A[i];
    for (int j=1;(1<<j)<=n;j++ )
        for (int i=0;i+(1<<j)-1<n;i++ ) d[i][j]=min(d[i][j-1],d[i+(1<<j)-1][j-1]);
}

int RMQ(int L,int R)
{
    int k=0;
    while ( (1<<(k+1)) <=R-L+1 ) k++;
    return min(d[L][k],d[R-(1<<k)+1][k]);
}

/*----------------------------

          二分图
       返回最大匹配数

----------------------------*/

bool dfs(int u)
{
    for (int i=1;i<=n;i++) if (!vis[i] && g[u][i])
    {
        vis[i]=1;
        if (!link[i] || dfs(link[i]))
        {
            link[i]=u;
            return 1;
        }
    }
    return 0;
}

int solve()
{
    int ans=0;
    memset(link,0,sizeof(link));
    for (int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if (dfs(i)) ans++;
    }
    return ans;
}

/*-------------------------------------

              快速乘法
用于求a,b相乘mod m会爆long long的时候

--------------------------------------*/

LL multi(LL a,LL b,LL m) {
    LL ans=0;

    while(b)
    {
        if(b&1) ans=(a+ans)%m;
        a=(a*2)% m;
        b>>=1;
    }
    return ans;
}

/*-------------------------------------

         莫比乌斯反演
求(a,b)中有多少对(x,y)满足gcd(x,y)=d

-------------------------------------*/

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define maxn 50005

using namespace std;

int a,b,c,d,n,k,p[maxn],mu[maxn];
int cnt;
bool vis[maxn];

void setup(int high)
{
    mu[1]=1; cnt=0;
    for (int i=2;i<=high;i++)
    {
        if (!vis[i])
        {
            vis[i]=1; mu[i]=-1;
            p[cnt++]=i;
        }
        for (int j=0;j<cnt && i*p[j]<=high;j++)
        {
            vis[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else
            {
                mu[i*p[j]]=0;
                break;
            }
        }
    }
    for (int i=1;i<=high;i++) mu[i]+=mu[i-1];
}

int solve(int n,int m)
{
    int p,ans=0,last=0;
    n/=k; m/=k;
    p=min(n,m);
    for (int i=1;i<=p;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ans+=(mu[last]-mu[i-1])*(n/i)*(m/i);
    }
    return ans;
}

int main()
{
    setup(maxn-5);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%d\n",solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1));
    }
    return 0;
}

/**************************************************************
    Problem: 3884
    User: sd197555
    Language: C++
    Result: Accepted
    Time:1748 ms
    Memory:89180 kb
****************************************************************/

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long long
#define maxn 10000005

using namespace std;

int prime[maxn],phi[maxn],cnt;
bool vis[maxn];
LL p;

void setup(int high)
{
    memset(prime,0,sizeof(prime));
    memset(vis,0,sizeof(vis));
    memset(phi,0,sizeof(phi));
    cnt=0;
    phi[1]=1;
    for (int i=2;i<=high;i++)
    {
        if (!vis[i])
        {
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for (int j=0;j<cnt && prime[j]*i<=high;j++)
        {
            vis[i*prime[j]]=1;
            if (i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}

LL pow_mod(LL a,LL b,LL mod)
{
    LL ans=1;
    while (b)
    {
        if (b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

LL solve(LL p)
{
    if (p==1) return 0;
    LL c=(LL) solve(phi[p])+phi[p];
    return pow_mod(2, c , p);
}

int main()
{
    int T;
    setup(maxn-5);
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld",&p);
        printf("%lld\n",solve(p));
    }
    return 0;
}