#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

void change(int a,string s1,int b,string &s2)

{

vector<int>num;

for(int i=0;i<s1.size();i++){

if(s1[i]<='9') num.push_back(s1[i]-'0');

else if(s1[i]<='Z') num.push_back(s1[i]-'A'+10);

else num.push_back(s1[i]-'a'+36);

}

reverse(num.begin(),num.end());

while(num.size()){

int r=0;

for(int i=num.size()-1;i>=0;i--){

num[i]+=r*a;

r=num[i]%b;

num[i]/=b;

}

ans.push_back(r);

while(num.size()&&num.back()==0)

num.pop_back()

}

reverse(ans.begin(),ans.end());

for(int i=0;i<ans.size();i++){

if(ans[i]<=9) s2+=char(ans[i]+'0');

else if(ans[i]<=35) s2+=char(ans[i]-10+'A');

else s2+=char(ans[i]-36+'a');

}

}

int main()

{

ios::sync_with_stdio(false);

cin.tie(0);

int t;

cin>>t;

while(t--){

int a,b;

string s1,s2;

cin>>a>>b>>s1;

change(a,s1,b,s2);

cout<<a<<" "<<s1<<endl;

cout<<b<<" "<<s2<<endl;

cout<<endl;

}

return 0;

}