#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000char s[10000];int start[10000];int res[10000];int ans[10000];int getnum(char c){    if(c>=‘a‘)        return c-‘a‘+36;    if(c>=‘A‘)        return c-‘A‘+10;    return c-‘0‘;}char getchar(int n){    if(n>=36)        return ‘a‘+n-36;    if(n>=10)        return ‘A‘+n-10;    return ‘0‘+n;}void trans(char* str,int base0,int base1){    memset(res,0,sizeof(res));    int y,i,j;    start[0]=strlen(str);    for(i=1;i<=start[0];i++)    {        start[i]=getnum(str[i-1]);    }    while(start[0]>=1)    {        y=0; //余数        ans[0]=start[0];        for(i=1;i<=start[0];i++)        {            y=y*base0+start[i];            ans[i]=y/base1;            y%=base1;        }        res[++res[0]]=y;  //这一轮的余数        i=1;        while(i<=ans[0]&&ans[i]==0)            i++;        memset(start,0,sizeof(start));        for(j=i;j<=ans[0];j++)            start[++start[0]]=ans[j];        memset(ans,0,sizeof(ans));    }    return;}void output(){    for(int i=res[0];i;i--)        printf("%c",getchar(res[i]));    printf("\n");}int main(){    #ifndef ONLINE_JUDGE        freopen("shu.txt","r",stdin);    #endif    int t;    scanf("%d",&t);    while(t--)    {        int x,y;        scanf("%d%d%s",&x,&y,s);        trans(s,x,y);        printf("%d %s\n",x,s);        printf("%d ",y);        output();        printf("\n");    }    return 0;}