#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,m;
	string s;
	cin>>n;
	for(int i=0;i<n;i++){
		long long k=0;
		cin>>m;
		getchar();
		getline(cin,s);
		for(int i=s.size()-1,l=0;i>=0;i--,l++){
			if(s[i]>='A'){
				k+=(s[i]-'A'+10)*pow(m,l);
			}else{
				k+=(s[i]-'0')*pow(m,l);
			}
		}
		cout<<k<<endl;
	}
	return 0;
}