#include<bits/stdc++.h>
#define int long long
using namespace std; 

int n, k, len, ans; 
string s; 

int f(char c){
	if(c >= '0' and c <= '9'){
		return c - '0'; 
	}
	return c - 'A' + 10; 
}

int g(int x, int y){
	int sum = 1; 
	for(int i = 1; i <= y; i++){
		sum *= x; 
	}
	return sum; 
}

signed main(){
	scanf("%d", &n); 
	while(n--){
		scanf("%d", &k); 
		cin >> s; 
		len = s.size(); 
		ans = 0;  
		
		for(int i = 0; i < len; i++){
			ans += f(s[i]) * g(k, len - i - 1); 
		}
		
		printf("%d\n", ans); 
	}
	return 0; 
}