#include <bits/stdc++.h>
using namespace std;
long long a[15];
int n, k;
int main() {
	int t;
	cin >> t;
	while (t--) {
		string s;
		cin >> k >> s;
		n = s.size();
		for (int i = 0; i < n; i++) {
			a[i] =  s[i] - '0';
			if (s[i] >= 'A' && s[i] <= 'Z') a[i] = s[i] - 'A' + 10;
		} // 存储为数组 
		long long t = 1;
		for (int i = n - 1; i >= 0; i--) {
			a[i] *= t;
			t *= k;
		} // 权重相乘 
		for (int i = n - 1; i >= 0; i--) { 
			a[i + 1] += a[i] / 10;
			a[i] %= 10;
		} // 进位
		int j = 0;
		while (a[j] == 0 && j < n - 1) 
			j++; 
		for (int i = j; i < n; i++) 
			cout << a[i];
		cout << endl;
	}
	return 0;
}