#include <stdio.h>
#include <string.h>
const int L=1001;
const char need[62]={
      '0','1','2','3','4','5','6','7','8','9',
      'A','B','C','D','E','F','G','H','I','J',
      'K','L','M','N','O','P','Q','R','S','T',
      'U','V','W','X','Y','Z','a','b','c','d',
      'e','f','g','h','i','j','k','l','m','n',
      'o','p','q','r','s','t','u','v','w','x',
      'y','z'};
char a[L],b[L];
short t,n,m,len;

void solve(void){
     int s,start,ans=0;
     bool sign;
     while (len>0){
           start=0,sign=false,s=0;
           for (int i=1;i<=len;i++){
               s=(s*n+a[i]);
               if (s>=m)sign=true;
               if (sign)a[++start]=s/m;
               s%=m;
               //printf ("s:%d\n",s);
               }
           b[++ans]=s;
           len=start;
           }
     for (int i=ans;i>=1;i--)printf ("%c",need[b[i]]);
     }

int main(void){
    freopen ("1220.in","r",stdin);
    freopen ("1220.out","w",stdout);
    scanf ("%d",&t);
    for (int i=1;i<=t;i++){
        scanf ("%d%d%s",&n,&m,b+1);
        printf ("%d %s\n%d ",n,b+1,m);fflush(stdout);
        len=strlen (b+1);
        for (int i=1;i<=len;i++)
            if (b[i]>='0'&&b[i]<='9')a[i]=b[i]-'0';
            else if (b[i]>='A'&&b[i]<='Z')a[i]=b[i]-55;
                 else a[i]=b[i]-61;
        solve();
        printf ("\n\n");
        }
    return 0;
    }