#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long LL;
string m;
int n, k;

LL trans(int k, string m){
    LL res = 0;
    for(char c:m){
        int val = (isdigit(c)?c-'0':toupper(c)-'A' +10);
        res = res * k + val;
    }
    return res;
}


LL trans(int k, string m){
    LL res = 0;
    int i = 1;
    for(char c:m){
        if(c > '9'){
            res += (c-'0' - 7) *pow(k,m.length() - i);
        }else{
            res += (c-'0') *pow(k,m.length() - i);
        }
        i++;
    }
    return res;
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> k >> m;
        cout << trans(k, m) << endl;
    }
    return 0;
}