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

int main() {
    int base,t;  // x进制,t个数 
    string numStr;  // 输入的数字字符串
    cin>>t;
	
	while (t>0){
		cin >> base >> numStr;
		
    	if (base == 10) {  // 特判：已经是十进制
    	    cout << numStr;
    	    return 0;
    	}
		
    	long long result = 0;
    	for (int i = 0; i < numStr.size(); ++i) {
    	    char c = numStr[i];
    	    int digit;
    	    
    	    // 处理数字字符
    	    if (c >= '0' && c <= '9') {
    	        digit = c - '0';
    	    } 
    	    // 处理字母字符（A-Z表示10-35）
    	    else if (c >= 'A' && c <= 'Z') {
    	        digit = c - 'A' + 10;
    	    }
    	    // 处理小写字母（a-z表示10-35）
    	    else if (c >= 'a' && c <= 'z') {
    	        digit = c - 'a' + 10;
    	    }
    	    
    	    // 计算当前位的值并累加
    	    result = result * base + digit;
    	}

 	    cout << result <<endl;
 	    t--;
	}
    return 0;
}