#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;
int a,x;
int bla[4]={1,2,4,16};
long long pow[2][20];

long long pot(int a,long long x,long long mod){
    if(x==0) return 1;
    long long ret=pot(a,x/2,mod);
    ret=ret*ret%mod;
    if(x%2==1) ret=ret*a%mod;
    return ret;
}

long long calc(int v,int a,int x,bool k,int n){
    if(v>=n) return 0;
    if(x==0 || a==1) return pow[k][v];
    if(a>2 && x>1) return 0;
    if(a==2 && x>3) return 0;
    if(x==1){
        if(n<=a*v) return 0;
        else return pow[k][a*v];
    }
    if(bla[x]*v>=n) return 0;
    else return pow[k][bla[x]*v];
}

int A,v;long long MOD;
int Na[2];
long long solve(int a,int x,int n[2],int mod){
    if(x==0) return 1;
    //if(x==1)printf("%d %d\n",n[0],n[1]);
    //printf("bla\n");
    long long r[2];
    for(int k=0;k<2;++k){
        r[k]=0;
        if(n[k]==0) continue;
        A=a;
        v=0;
        while(A>0 && A%pow[k][1]==0){
            A/=pow[k][1];
            ++v;
        }
        //if(x==1)printf("%d %d\n",n[0],n[1]);

        if(n[1]==0){
            Na[0]=n[0]-1;
            Na[1]=0;
            MOD=mod/2;
        }
        //if(x==1)printf("%d %d\n",n[0],n[1]); ova linija ovdje

        else{
            Na[0]=n[0]+1;
            Na[1]=n[1]-1;
            MOD=mod*2/5;
        }

        r[k]=pot(A,solve(a,x-1,Na,MOD),pow[k][n[k]]);
        if(a%pow[k][1]==0) r[k]=r[k]*calc(v,a,x-1,k,n[k])%pow[k][n[k]];
    //if(x==1)printf("%d %d\n",n[0],n[1]);

    }
    //if(x==2) printf("%lld %lld\n",r[1],r[0]);

    //if(x==1)printf("%d %d\n",n[0],n[1]);
    long long ret=0;
    if(n[0]!=0) ret+=pow[1][n[1]]*r[0]%mod*pot(pow[1][n[1]],pow[0][n[0]-1]-1,pow[0][n[0]])%mod;
    if(n[1]!=0) ret+=pow[0][n[0]]*r[1]%mod*pot(pow[0][n[0]],4*pow[1][n[1]-1]-1,pow[1][n[1]])%mod;
    //printf("x:%d ret:%lld n %d %d mod:%d\n",x,ret%mod,n[0],n[1],mod);
    return ret%mod;
}
int t,p,q;
int w[2];
int main(void){
    w[1]=9;
    w[0]=9;
    pow[0][0]=1;
    pow[1][0]=1;
    for(int i=1;i<20;++i){
        pow[0][i]=pow[0][i-1]*2;
        pow[1][i]=pow[1][i-1]*5;
    }
    scanf("%d",&t);
    for(int i=0;i<t;++i){
        scanf("%d%d",&p,&q);
        printf("%d\n",solve(p,q,w,1000000000));
    }
    scanf("%%");
return 0;
}