#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,sum;
ll k;
string a; 
ll poww(ll x,ll y){
	int ant=x;
	if(y<=0){
		return 1;
	}
	for(int i=0;i<y-1;i++){
		ant*=x;
	}
	return ant;
}

int main() {
	cin>>n;
	for(int i=0;i<n;i++){
		sum=0;
		cin>>k>>a;
		ll d=a.size();
		if(k<=10){
			if(k==10){
				cout<<a;
			}
			else{
				for(int j=0;j<d;j++){
					ll b=a[j]-'0';
					ll c=ll(poww(k,d-j-1));
					sum+=b*c;
				}
				cout<<sum<<endl;
			}
		}
		else{
			for(int j=0;j<d;j++){
				if(a[j]>='A' && a[j]<='Z'){
					ll b=a[j]-'0'-7;
					ll c=ll(poww(k,d-j-1));
					sum+=b*c;
					continue;
				}
				ll b=a[j]-'0';
				ll c=ll(poww(k,d-j-1));
				sum+=b*c;
			}
			cout<<sum<<endl;
		}
	}
	return 0;
}