#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int main(){
	ll a;
	cin>>a;
	while(a--){
		ll k,n=0;
		string x;
		cin>>k;
		cin>>x;
		if(k>=10){
			for(ll i=0;i<x.size();i++){
				n+=(x[i]-'0'*pow(k,i));
			}
		}if(k<10){
			for(ll i=0;i<x.size();i++){
				if(x[i]=='A'){
					n+=(10*pow(k,i));
				}else if(x[i]=='B'){
					n+=(11*pow(k,i));
				}else if(x[i]=='C'){
					n+=(12*pow(k,i));
				}else if(x[i]=='D'){
					n+=(13*pow(k,i));
				}else if(x[i]=='E'){
					n+=(14*pow(k,i));
				}else if(x[i]=='F'){
					n+=(15*pow(k,i));
				}else{
					n+=(x[i]-'0'*pow(k,i));
				}
			}
		}cout<<n<<endl;
	}return 0;
}