#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxs = 1000;
int oldBase,newBase;//原进制,新进制
char origin[maxs];//原串
int str[maxs],ans[maxs],goal[maxs];//被除数,除数,结果数组 //将单个字符转变为数字
int getNum(char ch)
{
if(ch>='0'&&ch<='9')//数字
return ch-'0';
if(ch>='A'&&ch<='Z') //大写字母
return ch-'A'+10;
return ch-'a'+36;//小写字母
}
//将数字转变为字符
char getchar(int num)
{
if(num>=0&&num<=9)
return num+'0';
if(num>=10&&num<=35)
return num-10+'A';
return num-36+'a';
}
void trans()
{
memset(goal,0,sizeof(goal));//初始化结果数组
//初始化,把输入的字符串转变为对应的数字
int len = strlen(origin);
str[0] = len; //str[0]存储字符串的长度
for(int i=0;i<len;i++)
str[i+1]=getNum(origin[i]);
while(str[0]>=1)//被除数还没有为0,继续短除法
{
memset(ans,0,sizeof(ans));//ans[0]代表商的位数
int y=0,i;//余数
for(i=1;i<=str[0];i++)//手动模拟除法
{
y=y*oldBase+str[i];
ans[++ans[0]]=y/newBase;
y=y%newBase;
}
goal[++goal[0]]=y;//第一轮短除法结束,得到的余数 //得到第二轮短除法的被除数,也就是上一轮的商,但是要去除前导0
i=1;
while(i<=ans[0]&&ans[i]==0)
i++;
memset(str,0,sizeof(str));
for(;i<=ans[0];i++)
str[++str[0]]=ans[i];
}
//输出结果
for(int i=goal[0];i>=1;i--)
printf("%c",getchar(goal[i]));
printf("\n");
}
int main()
{
freopen("in.txt","r",stdin);
int T;
cin>>T;
while(T--)
{
scanf("%d%d",&oldBase,&newBase);
scanf("%s",origin);
printf("%d %s\n%d ",oldBase,origin,newBase);
trans();
printf("\n");
} }

  

04-30 07:30