#include <bits/stdc++.h>
#define in long long
//#include <stdio.h>
using namespace std;
/*
inline in read(){
	in x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return (x * f);
}
*/
in ch_of_num_list[205];
inline in zhuan(string s, in k){
	in tmp = 0, ans = 0;	
	for(in i = s.size(); i >= 0; i++){
		if(s[i] >= '0' && s[i] <= '9') ans += (s[i] - '0') * pow(k, tmp);
		else ans += ch_of_num_list[s[i]] * pow(k, tmp);
		tmp++;
	}
	return ans;
}
inline void valueadd(){
	in tmp = 10;
	for(in i = 'A'; i <= 'F'; i++){
		ch_of_num_list[i] = tmp;
		tmp++;
	}
	return;
}
int main(){
	valueadd();
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	in n, k;
	string s;
	//n = read();
	cin >> n;
	while(n--){
		cin >> k >> s; // = read();
		if(k == 10) cout << s;
		else cout << zhuan(s, k) << endl;
	}
	return 0;
}