#include<bits/stdc++.h>
#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i<=b;++i)
#define yes(i,a,b) for(Rg int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
using namespace std;
il int read()
{
    Rg int x=0,y=1;char c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=(x<<1)+(x<<3)+c-‘0‘;c=getchar();}
    return x*y;
}
const int N=1010;
int T,n,a,b,ct,d[N],as[N];
int main()
{
    T=read();
    while(T--)
    {
        ct=0;a=read(),b=read();
        string s;cin>>s;n=s.length();
        go(i,1,n)
        {
            char c=s[i-1];
            if(c>=‘0‘ && c<=‘9‘)d[n-i+1]=c-‘0‘;
            if(c>=‘A‘ && c<=‘Z‘)d[n-i+1]=c-‘A‘+10;
            if(c>=‘a‘ && c<=‘z‘)d[n-i+1]=c-‘a‘+36;
        }
        while(n)
        {
            yes(i,n,2){d[i-1]+=d[i]%b*a;d[i]/=b;}
            as[++ct]=d[1]%b;d[1]/=b;
            while(n && !d[n])n--;
        }
        printf("%d ",a);cout<<s<<endl;printf("%d ",b);
        yes(i,ct,1)
        {
            Rg int c=as[i];
            if(c>=0 && c<=9)printf("%d",c);
            if(c>=10 && c<=35)printf("%c",(char)(c-10+‘A‘));
            if(c>=36 && c<=61)printf("%c",(char)(c-36+‘a‘));
        }
        printf("\n\n");
    }
    return 0;
}