#include<bits/stdc++.h>
using namespace std;
long long po(int x,int y){
	long long sum=1;
	for(int i=1;i<=y;i++)
		sum*=x;
	return sum;
}
void way_one(int k,string x){
	int sum=0,cnt=0,q=x.size()-1;
	while(q>=0)
	{
		long long t=po(k,cnt);
		sum+=(x[q]-'0')*t;
		cnt++;
		q--;
	}
	cout<<sum<<endl;
}
void way_two(int k,string x){
	int sum=0,cnt=0,q=x.size()-1;
	while(q>=0)
	{
		long long t=po(k,cnt);
		if(x[q]>='A'&&x[q]<='F')
			sum+=(x[q]-'A'+10)*t;
		else	
			sum+=(x[q]-'0')*t;
		cnt++;
		q--;
	}
	cout<<sum<<endl;
}
int main()
{
	int n;
	cin>>n;
	while(n--){
		int k;
		string x;
		cin>>k>>x;
		if(k<=10) way_one(k,x);
		else way_two(k,x);
	}
	return 0;
}