#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin >> n;
	for(long long l=1;l<=n;l++)
	{
		long long m,k=0;
		string s;
		cin >> m >> s;
		if(m!=16)
		{
			for(long long l=0;l<s.size();l++)
			{
				long long x=s[s.size()-1-l]-'0';
				k=k+x*pow(m,l);
			}
			cout << k << endl;
		}
		else
		{
			for(long long l=0;l<s.size();l++)
			{
				long long x;
				if(s[s.size()-1-l]>='A'&&s[s.size()-1-l]<='F')
				{
					x=s[s.size()-1-l]-55;
				}
				else
					x=s[s.size()-1-l]-'0';
				k=k+x*pow(m,l);
			}
			cout << k << endl;
		}
	}
	return 0;
}