#include <bits/stdc++.h>
using namespace std;
long long a[15];
int n, k;
void Node (long long a[]) {
	long long s = 1;
	for (int i = n; i >= 1; i--) {
		a[i] *= s;
		s *= k;
	}
	for (int i = n; i >= 1; i--) {
		if (a[i] >= k) {
			a[i - 1] = a[i] / k;
			a[i] -= a[i - 1] * k;
		}
	}
	if (a[0]) {
		for (int i = 0; i <= n; i++) {
			if (a[i] >= 10) cout << char (a[i] - 10 + 'A');
			else cout << a[i];
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (a[i] >= 10) cout << char (a[i] - 10 + 'A');
			else cout << a[i];
		}
	}
	cout << endl;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> k >> s;
		n = s.size();
		for (int i = 1; i <= n; i++) {
			if (s[i - 1] >= 'A' && s[i - 1] <= 'Z') a[i] = 10 + s[i - 1] - 'A';
			else a[i] =  s[i - 1] - '0';
		}
		if (k == 10) cout << s << endl;
		else Node (a);
	}
	return 0;
}