#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int k,ans=0;cin>>k;
		if(k!=16){
			int s;cin>>s;
			int t=0;
			while(s!=0){
				int p=s%10;
				ans+=p*pow(k,t);
				s/=10;
				t++;
			}
		}
		else{
			string s;cin>>s;
			int l=s.size(),p=0;
			for(;l>0;l--,p++){
				int i=0;
				if(s[l-1]>='A'&&s[l-1]<='G'){
					i=s[l-1]-55;
				}else{
					i=s[l-1]-'0';
				}
				ans+=i*pow(k,p);
			}
		}
		cout<<ans;
	}
}