#include<iostream>
using namespace std;
int f(string s,int n){
	int la=s.length();
	int sum=0;int x=1;
	for(int i=la-1;i>=0;i--){
		if('0'<=s[i]&&s[i]<='9'){
		sum+=(int)(s[i]-'0')*x;
		x*=n;
		}
		else {
		sum+=(int)(s[i]-'A'+10)*x;
		x*=n;
		
		}
	}
	return sum;
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		string s;
		cin>>a>>s;
		cout<<f(s,a)<<endl;
	}
	return 0;
}