#include<bits/stdc++.h>
using namespace std;
int z(char y)
{
	int g;
	if (y>='0'&&y<='9')
		g=int(y)-48;
	else
		g=int(y)-55;
	return g;
} 
void h(int k,string x)
{
	int s=0,i=x.size()-1,j=0;
	while (i>=0)
	{
		s=s+z(x[i])*pow(k,j);
		i--;
		j++;
	}
	cout<<s<<endl;
}
int main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int k; 
		string x;
		cin>>k;
		cin>>x;
		h(k,x);
	}
	return 0;
}