#include<bits/stdc++.h>
using namespace std;
long long n,a,sum;
string s;
int main()
{
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		cin>>a>>s;
		sum=0;
		for(long long k=0,j=s.size()-1;j>=0;j--,k++)
		{
			switch(s[j])
			{
				case 'A':sum+=10*pow(a,k);break;
				case 'B':sum+=11*pow(a,k);break;
				case 'C':sum+=12*pow(a,k);break;
				case 'D':sum+=13*pow(a,k);break;
				case 'E':sum+=14*pow(a,k);break;
				case 'F':sum+=15*pow(a,k);break;
			}
			if(s[j]!='A'&&s[j]!='B'&&s[j]!='C'&&s[j]!='D'&&s[j]!='E'&&s[j]!='F')
		    {
		    	sum+=(s[j]-'0')*pow(a,k);
			} 
		}
		cout<<sum<<endl;
	}
	return 0;
}

16进制单独判断，其他转为数字乘（从后往前的位数和数字）的次方