/*
g++ -o2 SP10050.cpp -o c -std=c++14
.\c

*/

#include<cstdio>

using namespace std;
typedef long long ll;
typedef __int128 in;

const ll N=5e3+100;
const ll MOD=1e9;
ll flg;

char *p1,*p2;
char buf[N];

#define nc() getchar()
// #define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)

void read(ll &x){
    ll sum=0;
    ll f=1;
    char ch=nc();
    while(ch<48 || ch>57){
        ch=nc();
    }
    while(ch>=48 && ch<=57){
        sum=(sum<<1)+(sum<<3)+ch-48;
        ch=nc();
    }
    x=sum;
    return ;
}

void write(ll x,ll idx){
    if(idx==10)return ;
    write(x/10,idx+1);
	putchar(x%10+'0');
}

ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}

in pow(in a,in b,ll p){
    in sum=1;
    while(b){
        if(b&1){
            sum=sum*a;
            sum=sum>=p?sum%p+p:sum;
        }
        a=a*a;
        a=a>=p?a%p+p:a;
        b>>=1;
    }
    return sum%p;
}

ll ask(ll m){
    ll sum=m;
    if(m==1)return 1;
    for(ll i=2;i*i<=m;i++){
        if(m%i==0){
            sum=sum/i*(i-1);
            while(m%i==0)m/=i;
        }
    }
    return m>1?sum/m*(m-1):sum;
}

bool check(ll a,ll b){
    if(b>=5)return 1;
    else if(b==4){
        if(a>2)return 1;
        return 0;
    }
    else if(b==3){
        if(a>=3)return 1;
        return 0;
    }
    else if(b==2){
        if(a>=10)return 1;
        return 0;
    }
    return 0;
}

ll t;
ll a,b;
ll mul[N];
ll phi[N];

void init(){
    phi[1]=MOD;
    for(ll i=2;i<=min(b,32)+1000;i++){
        phi[i]=ask(phi[i-1]);
    }
    return ;
}

int main(){
    // read(t);
    scanf("%lld",&t);
    while(t--){
        // read(a);
        // read(b);
        scanf("%lld%lld",&a,&b);
        flg=check(a,b);
        if(a==1){
            printf("1\n");
            continue;
        }
        if(a==0){
            if(b%2==0)printf("1\n");
            else printf("0\n");
            continue;
        }
        if(b==0){
            printf("1\n");
            continue;
        }
        if(b==1){
            printf("%lld\n",a);
            continue;
        }
        // for(ll i=1;i<=min(b,32);i++)mul[i]=a;
        init();
        in sum=1;
        for(ll i=min(b,32);i>=1;i--){
            if(phi[i]==1){
                sum=1;
                continue;
            }
            sum=pow(a,sum,phi[i]);
            if(sum==1)sum+=phi[i];
            if(sum==0)sum+=phi[i];
        }
        ll s=sum%MOD;
        // print(s);
        if(flg)printf("...%09lld\n",s);
        else printf("%lld\n",s);
    }
    return 0;
}