#include<bits/stdc++.h>
#include<cstring>
#include<string>
using namespace std;
long long n,k,x,j;
string s;
int main(){
	cin>>n;
    for(int i=1;i<=n;i++){
    	cin>>k>>s;
    	if(k==10){
    		cout<<s<<endl;
    		continue;
		}j=x=0;
		for(int f=s.size()-1;f>=0;f--){
	    	switch(s[f]){
				case 'A':x+=10*pow(k,j);
				case 'B':x+=11*pow(k,j);
				case 'C':x+=12*pow(k,j);
				case 'D':x+=13*pow(k,j);
				case 'E':x+=14*pow(k,j);
				case 'F':x+=15*pow(k,j);
				case '1':x+=1*pow(k,j);
				case '2':x+=2*pow(k,j);
				case '3':x+=3*pow(k,j);
				case '4':x+=4*pow(k,j);
				case '5':x+=5*pow(k,j);
				case '6':x+=6*pow(k,j);
				case '7':x+=7*pow(k,j);
				case '8':x+=8*pow(k,j);
				case '9':x+=9*pow(k,j);
			}
			j++;
		}cout<<x<<endl;
	}
	return 0;
}