#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	int k;
	string a;
	cin >> n;
	long long sum = 0;
	int m = 0;
	for (int i = 1; i <= n; i++) {
		cin >> k >> a;
		sum=0;
		int s = a.length();
		if (k <=10) {
			for (int j = s-1; j >= 0; j--) {
				
				sum += (a[j]-'0')* pow(k,s-j-1);

			}
			cout << sum;
		}
		else {
			for (int j = s-1; j >= 0; j--) {
				if (a[j]>='A'&&a[j]<='Z') {
					m = a[j]-'A' + 10;
					a[j] = m;
				}
				
				else {
					m=a[j]-'0';
					a[j]=m;
				}
				sum+=a[j]*pow(k,s-j-1);

			}
			cout<<sum;
		}

	}
		return 0;
	}