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