#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,n;
	string k;
	cin>>a;
	for(int i=1;i<=a;i++){
		cin>>n>>k;
		int sum=0;
		for(int j=0;j<k.size();j++){
			if(k[j]<='9')
				k[j]-='0';
			else
				k[j]=k[j]-'A'+10;
			sum+=pow(n,k.size()-j-1)*k[j];
		}
		cout<<sum<<endl;
	}
	return 0;
}