#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#define LL long longusing namespace std;int get_phi(int n){ int ans=n,w=sqrt(n); for (int i=2;i<=w;i++) if (n%i==0) { ans=ans/i*(i-1); while (n%i==0) n/=i; } if (n>1) ans=ans/n*(n-1); return ans;}int ksm(int x,int y,int p){ if (!y) return 1; if (y==1) return x; int w=ksm(x,y/2,p); w=(LL)w*w%p; if (y%2==1) w=(LL)w*x%p; return w;}int solve(int p){ if (p<=1) return 0; int k=1,u=0; while (p%2==0) { k*=2;u++;p/=2; } int phi=get_phi(p); u%=phi; int re=(solve(phi)-u+phi)%phi; return ksm(2,re,p)%p*k;}int main(){ int T; scanf("%d",&T); while (T--) { int p; scanf("%d",&p);
