答案：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=10;
int a[10];
char ch[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
void solve()
{int n,m;cin>>n>>m;string str;cin>>str;for(int i=0;i<str.size();i++){if(str[i]>='0'&&str[i]<='9'){a[i]=str[i]-'0';}else{a[i]=str[i]-'A'+10;}}int x=0;//x 是要被转换的十进制数。for(int i=0;i<str.size();i++){x=x*n+a[i];}string ans;//ans 是一个字符串，用来存储转换后的结果while(x){ans+=ch[x%m];//m是目标进制的基数。计算 x 除以m的余数。这个余数就是当前位在目标进制中的值。x/=m;//整除m来更新x。这一步相当于移位，准备计算下一位。}reverse(ans.begin(),ans.end());/*因为在循环过程中，每次取出的字符都是从低位到高位，所以最终结果 ans 是反向的。
使用 reverse 函数将 ans 反转，使其变为正确的高位在前、低位在后的顺序。*/cout<<ans<<"\n";
}int main()
{int t;cin>>t;while(t--)solve();return 0;
}