#include "bits/stdc++.h"
using namespace std;
int poww(int a,int b){
	return b==0?1:pow(a,b);
}
int main(void){
	int T;
	cin>>T;
	while(T--){
		int m,ans=0;
		string st;
		cin>>m>>st;
		for(int i=0;i<st.length();i++)
			if(st[i]>='0' && st[i]<='9') ans+=poww(m,st.length()-i-1)*(st[i]-'0');
			else ans+=pow(m,st.length()-i-1)*(st[i]-'A'+10);
		cout<<ans<<'\n';
	}
}