#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
long long hs(long long k,string s)
{
	long long zong,wei=s.length()-1 ;
	long long huan;
	for(int i=1;i<=s.length() ;i++)
	{
		if(s[i]=='A')
	    {
	         huan=10;
		}
		if(s[i]=='B')
	    {
	         huan=11;
		}
		if(s[i]=='C')
	    {
	         huan=12;
		}
		if(s[i]=='D')
	    {
	         huan=13;
		}
		if(s[i]=='E')
	    {
	         huan=14;
		}
		if(s[i]=='F')
	    {
	         huan=15;
		}
		else
		{
			huan=s[i]-'0';
		}
		zong+=huan*pow(k,wei);
		wei--; 
	}
	return zong;
}
int main()
{
	ios::sync_with_stdio(0);
	long long n,k1;
	string a;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>k1>>a;
		cout<<hs(k1,a)<<endl;
	}
   
}