#include<bits/stdc++.h>
using namespace std;
int n,x;
string y;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a[21];
        unsigned long long ans=0;
        cin>>x>>y;
        for(int j=y.size()-1;j>=0;j--)
            if(y[j]>='0' and y[j]<='9')a[y.size()-j]=y[j]-'0';
            else a[j+1]=y[j]-'A'+10;
        for(int j=1;j<=y.size();j++)
        {
            unsigned long long s=pow(x,j-1);
            ans+=a[j]*s;
        }
        cout<<ans<<endl;
    }
    return 0;
}