#include <bits/stdc++.h>                 // [PRIMES]               1777 ~2^10.80
using namespace std;                     //                       10333 ~2^13.33
using ll = long long;                    // seq 1 128 | factor   100333 ~2^16.61
using vl = vector<ll>;                   //   | grep -v ' .* '  1300111 ~2^20.31
using vvl = vector<vl>;                  //                    10300777 ~2^23.30
using pll = pair<ll,ll>;                 //                   100400999 ~2^26.58
using vb = vector<bool>;                 //                  1300400999 ~2^30.28
const ll oo = 0x3f3f3f3f3f3f3f3fLL;      //                 10200500333 ~2^33.25
const double eps = 1e-9;                 //                100200400777 ~2^36.54
#define sz(c) ll((c).size())             //               1200300700111 ~2^40.13
#define all(c) begin(c),end(c)           //              10200300500777 ~2^43.21
#define mp make_pair                     //             100200300400777 ~2^46.51
#define mt make_tuple                    //            1200300400600999 ~2^50.09
#define pb push_back                     //           10200300400600111 ~2^53.18
#define eb emplace_back                  //          100200300400600333 ~2^56.48
#define xx first                         //         1200300400500800999 ~2^60.06
#define yy second                       
#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (int i=(a); i<(b); i++)       
#define FORD(i,a,b) for (int i=int(b)-1; i>=(a); i--)
/// ({ ... }) avoids some problems: http://kernelnewbies.org/FAQ/DoWhile0
/// In non-contest code it is probably better to use: do { ... } while(0)
#define DBGDO(X) ({ if(1) cerr << "DBGDO: " << (#X) << " = " << (X) << endl; })

ll charToValue(char s){
	if(s - '0' >= 0 && '9' - s >= 0)
		return s -'0';
	else
		return 10 + s - 'A';
}

char valueToChar(int s){
	if(s < 10)
		return '0' + s;
	else
		return 'A' + s - 10;
}

ll getDecimal(string number, int sys){
	ll result = 0;
	for(unsigned int i =  0; i < number.length(); i++){
		result += charToValue(number.at(i)) * pow(sys, number.length()-i-1);	
	}
	return result;
}

string decimalToOther(ll num, int sys){
	if(num == 0)
		return "0";
	//get highest potenz, die gerade noch reinpasst
	int o = 0;
	while(pow(sys, o) <= num){
		o++;
	}
	o--;
	//cout << o << endl;
	//checke wie oft die Zahl reinpasst und subtrahiere das dann
	string result = "";
	for(int h = o; h >= 0; h--){
		ll pot = pow(sys, h);
		int wieoft = floor(num/pot);
		//cout << pot << " " << wieoft << endl;
		num -= wieoft*pot;
		result += valueToChar(wieoft);
	}
	return result;
}

string compute(int baseA, int baseB, string number){
	ll val = getDecimal(number, baseA);
	return decimalToOther(val, baseB);
}

int main() {
	ios::sync_with_stdio(false);
	//cout << compute(10, 35, "1") << endl;
	
	int testcases;
	cin >> testcases;
	FOR(i, 0, testcases){
		int baseA, baseB;
		cin >> baseA >> baseB;
		string number;
		cin >> number;
		cout << compute(baseA, baseB, number) << endl;
	}
}