#include <iostream>
using namespace std;
 
long long int strange(long long int s){
    long long int sum=0,n;
    while(s>9){
        n=s;
        sum=0;
        while(n>0){
            sum+=n%10;
            n/=10;
        }
        s=sum;
    }
    return s;
}
long long int power(long long int a,long long int b){
    long long int c;
    if(b==1)
	    return strange(a);
	long long int ans=power(a,b/2);    
	    if(b%2==0){
	        c=strange(ans*ans); 
	    }
	    else{
//	        c=strange(a*ans*ans);
	        c=strange(ans*(strange(ans*strange(a))));
	    }
	    return c;
	}
int main()
{
    int t;
    long long int a,n,f,ans;
    cin>>t;
    while(t--){
        cin>>a>>n;
        ans=power(a,n);
        cout<<ans<<endl;
    }
    return 0;
}