答案：

#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;
}