#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int tN(char c){
	if(c <= '9' && c >= '0') return c-'0';
	if(c <= 'Z' && c >= 'A') return c-'A'+10;
	return c-'a'+36;
}

char tC(int i){
	if(i < 10) return i+'0';
	if(i < 36) return i-10+'A';
	return i-36+'a';
}

int main() {
	int cases;
	cin >> cases;
	for(int ii = 0; ii < cases; ii++){
		int A,B;
		string s;
		cin >> A >> B >> s;
		int len = s.length();
		int *resI = new int[len * 62];
		for(int i = 0; i < len*62; i++) resI[i] = 0;
		int place = 0;
		for(int i = 0; i < len; i++){
			if(i != 0){
				//*A
				int carry = 0;
				for(int j = 0; j <= place; j++){
					resI[j] *= A;
					resI[j] += carry;
					carry = resI[j]/B;
					resI[j] %= B;
				}
				while(carry > 0){
					resI[place+1] = carry;
					carry /= B;
					resI[place+1] %= B;
					place++;
				}
			}
			resI[0] += tN(s[i]);

			if(i == len-1){
				int carry = 0;
				for(int j = 0; j <= place; j++){
					resI[j] += carry;
					carry = resI[j]/B;
					resI[j] %= B;
					if(carry == 0) break;
				}
				while(carry > 0){
					resI[place+1] = carry;
					carry /= B;
					resI[place+1] %= B;
					place++;
				}
			}

		}
		cout << A << ' ' << s << endl;
		cout << B << ' ';
		for(int i = place; i >= 0; i--){
			cout << tC(resI[i]);
		}
		cout << endl << endl;
		delete [] resI;
	}
	return 0;
}