int i,l,k,a,b,T,t[],A[];

char s[],d[];

main(){

    for(scanf("%d",&T);T--;){

        scanf("%d%d%s",&a,&b,s);

        for(k=i=strlen(s);<i--;)t[k--i]=s[i]-(s[i]<?:s[i]<?:);

        for(l=;k;){

            for(i=k;<i--;){

                t[i-]+=t[i]%b*a;

                t[i]/=b;

            }

            A[l++]=t[]%b;

            t[]/=b;

            for(;<k&&!t[k-];k--);

        }

        for(d[l]=i=;i<l;i++)d[l--i]=A[i]+(A[i]<?:A[i]<?:);

        printf("%d %s\n%d %s\n\n",a,s,b,d);

    }

}