#include<iostream>
#include<cstring>
using namespace std;
char a[1000];
int s[1000];
int b[1000];
int n,m;
void setin(){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	cin>>n>>m;
	cin>>a;
	cout<<n<<" "<<a<<endl;
	cout<<m<<" ";
}

void solve(){
	int l,i,j=0;
	l=strlen(a);
	for(i=0;i<l;i++){
if(a[i]>='0' && a[i]<='9')
	s[i]=a[i]-'0';
else if(a[i]>='A' && a[i]<='Z')
	s[i]=a[i]-'A'+10;
else if(a[i]>='a' && a[i]<='z')
	s[i]=a[i]-'a'+36;
	}
	while(1){
int t=0;
for(i=0;i<l;i++){
	if(s[i]!=0 && i<l-1){
s[i+1]+=(s[i]%m)*n;
s[i]=s[i]/m;
	}
	if(i==l-1)   {
b[j++]=s[i]%m;
s[i]=s[i]/m;
	}
}
for(i=0;i<l;i++)
	if(s[i]!=0) {
t=1;
break;
	}
	if(t==0)  break;
	}
	for(i=j-1;i>=0;i--){
if(b[i]>=0 && b[i]<=9)
	cout<<(char)(b[i]+'0');
else if(b[i]>=10 && b[i]<=35)
	cout<<(char)(b[i]+'A'-10);
else if(b[i]>=36 && b[i]<=61)
	cout<<(char)(b[i]+'a'-36);
	}
	cout<<endl<<endl;;
}
int main(){
	int round;
	cin>>round;
	while(round--){
setin();
solve();
	}
	return 0;
}