#include using namespace std; bool MillerRabin(long long n,vector A){ long long D,s,t,d,x; uint64_t mod=n,imod=n,t128=-__uint128_t(n)%n,m1; s=__builtin_ctzll(n-1); D=n-1>>s; for(int i=0;i<5;i++) imod*=2-mod*imod; imod=-imod; m1=(t128+__uint128_t(t128*imod)*mod)>>64; if(m1>=n) m1-=n; for(auto a:A){ if(n<=a) return true; a=(__uint128_t(a)*t128+__uint128_t(a*t128*imod)*mod)>>64; if(a>=mod) a-=mod; x=m1; for(d=D;d>0;d>>=1){ if(d&1){ x=(__uint128_t(a)*x+__uint128_t(a*x*imod)*mod)>>64; if(x>=mod) x-=mod; } a=(__uint128_t(a)*a+__uint128_t(a*a*imod)*mod)>>64; if(a>=mod) a-=mod; } if(x!=m1){ for(t=0;t>64; if(x>=mod) x-=mod; } if(t==s) return false; } } return true; } bool IsPrime(long long n){ if(n<=1) return false; else if(n==2) return true; else if(n%2==0) return false; else if(n<4759123141LL) return MillerRabin(n,{2,7,61}); else return MillerRabin(n,{2,325,9375,28178,450775,9780504,1795265022}); } long long FindPrimeFactor(long long n){ if(n%2==0) return 2; uint64_t mod=n,imod=n; for(int i=0;i<5;i++) imod*=2-mod*imod; imod=-imod; long long m=pow(n,0.15)+1,y,g,q,r,k,x,ys,d,c=1; auto f=[&](long long v){ v=(__uint128_t(v)*v+__uint128_t(v*v*imod)*mod)>>64; if(v>=mod) v-=mod; v+=c; if(v>=mod) v-=mod; return v; }; for(;true;c++){ y=k=0; g=r=1; for(;g==1;){ x=y; for(;4*k<3*r;k++) y=f(y); for(;ky?x-y:y-x; q=(__uint128_t(q)*d+__uint128_t(q*d*imod)*mod)>>64; if(q>=mod) q-=mod; } g=gcd(q,n); k+=m; } k=r; r*=2; } if(g==n){ g=1; y=ys; for(;g==1;){ y=f(y); g=gcd(x>y?x-y:y-x,n); } } if(g==n) continue; else if(IsPrime(g)) return g; else if(IsPrime(n/g)) return n/g; else return FindPrimeFactor(g); } } vector Factorize(long long n){ vector ret; long long p; for(;!IsPrime(n)&&n>1;){ p=FindPrimeFactor(n); for(;n%p==0;){ n/=p; ret.push_back(p); } } if(n>1) ret.push_back(n); sort(ret.begin(),ret.end()); return ret; } void solve(){ long long l; cin>>l; auto F=Factorize(l); long long p=F.back(); if(p==2){ long long r=l/4; cout<>t; while(t--) solve(); }