#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        char a;
        getchar();
        while (scanf("%c",&a) && a!='\n') 
        {
            if(a>='0'&&a<='9')v.push_back(a-'0');
            else v.push_back(a-'A'+10);
        }
        long long sum=0;
        int t=0;
        for(int j=v.size()-1;j>=0;j--)
        {
            sum+=v[j]*pow(x,t);
            t++;
        }
        cout<<sum<<endl;
        v.clear();
    }
}