请大佬求调

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1000000000;
int T;
ll a,b;
inline ll phi(ll n){
    ll res=1ll;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            int num=i-1;
            n/=i;
            while(n%i==0){
                num*=i;
                n/=i;
            }
            res*=num;
        }
    }
    if(n!=1) res*=n-1;
    return res;
}
inline ll qsm(ll x,ll y,ll p){
    ll res=1;
    while(y){
        if(y&1){
        	res*=x;
        	if(res>=p)res=res%p+p;
		}
        y>>=1;
        x=x*x;
        if(x>=p) x=x%p+p;
    }
    return res;
}
inline ll dfs(int x,long long num,ll p){
	//cout<<x<<" "<<p<<endl;
    if(p==1ll) return 1;
    if(x>b) return 1; 
    ll phip=phi(p);
    //cout<<phip;
    return qsm(num,dfs(x+1,num,phip),p);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
    	cin>>a>>b;
    	if(b==0)printf("1\n");
    	else if(b==1)printf("%d\n",a);
    	else if(a==0){
    		if(b&1)printf("0\n");
    		else printf("1\n");
		}
    	else{
    		ll ans=dfs(1,a,mod);
    		if(ans<mod) printf("%d\n",ans);
    		else printf("...%09d\n",ans%mod);
		}
	}
}