/*

前三位

len=log10n^k(乘积的长度)

len=klog10n

n^k=x*10^(len-1)

x=n^k/10^(len-1)

log10x = k*log10n - (len-1)

x=pow(10,k*log10n - (len-1))

后三位

快速幂解决

*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n,k,x;

ll power(ll a,ll n){

    ll res=;

    while(n){

        if(n%)res=res*a%;

        a=a*a%;

        n>>=;

    }

    return res%;

}

int main(){

    int T;

    cin>>T;

    for(int tt=;tt<=T;tt++){

        cin>>n>>k;

        ll len=k*log10((double)n);

        double x=pow((double),(double)k*log10((double)n)-(len-));

        while(x<)x*=;

        printf("Case %d: %d ",tt,(int)x);

        n%=;

        ll y=power(n,k);//后三位用快速幂

        if(y==)printf("000\n");

        else if(y<)printf("00%d\n",y);

        else if(y<)printf("0%d\n",y);

        else printf("%d\n",y);

    }

}