P4139被卡常了怎么办啊....

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int p;
int t;
int phi(int x)
{
    int ans=x;
    for(int i=2;i<=x;i++)
        if(x%i==0) 
        {
            ans/=i;ans*=i-1;
            while(x%i==0) x/=i;
        }
    if(x^1) ans/=x,ans*=x-1;
    return ans;
}
long long pow2(long long a,long long b,int p)
{
    long long res=1;
    for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;
    return res%p;
}
int work(int p)
{
    if(p==1) return 0;
    int num=0;
    while(~p&1) p>>=1,++num;
    int pi=phi(p);int now=work(pi);
    (now+=pi-num%pi)%=pi;
    now=pow2(2,now,p);
    return now<<num;
}
int main()
{
    scanf("%d",&t);
    while(t--) scanf("%d",&p),printf("%d\n",work(p));
    return 0;
}