#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 #define N  210000

 #define M  4100000

 #define fi first

 #define se second

 #define MP make_pair

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 const ll MOD=1e9+,inv2=(MOD+)/;

       double eps=1e-;

       ll INF=1e18;

       int dx[]={-,,,};

       int dy[]={,,-,};

 ll a[N],b[N],ans,n,k,mi[N];

 int len;

 ll read()

 {

    ll v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 ll calc(ll n)

 {

     if(n<) return ;

     int len=;

     while(n)

     {

         b[++len]=n%;

         n/=;

     }

     ll t=,re=;

     per(i,len,)

     {

         rep(j,,b[i]-)

         {

             if(i>=) re+=mi[i-]*(i-);

             if(j==k) re+=mi[i-];

             re+=mi[i-]*t;

         }

         if(b[i]==k) t++;

     }

     return re+t;

 }

 void dfs(int u,ll now,ll now_,int flag,int s)

 {

     if(u==)

     {

         if(calc(now)==now)

         {

             ans=now;

             return;

         }

     }

     if(s>=)

     {

         if(calc(now)-now<=&&calc(now_)-now_>=)

         {

             ll l=now,r=now_,last=now;

             while(l<=r)

             {

                 ll mid=(l+r)>>;

                 if(calc(mid)-mid<=){last=mid; l=mid+;}

                  else r=mid-;

             }

             if(calc(last)-last==) ans=max(ans,last);

         }

         return;

     }

     ll x=calc(now)-now,y=calc(now_)-calc(now),z=now-now_;

     if(x<&&x+y<) return;

     if(x>&&x+z>) return;

     if(flag)

     {

         per(i,,)

         {

             dfs(u-,now+mi[u-]*i,now+mi[u-]*(i+)-,,s+(i==k));

             if(ans!=-INF) return;

         }

     }

      else

      {

          dfs(u-,now+mi[u-]*a[u],now_,,s+(a[u]==k));

          if(ans!=-INF) return;

          per(i,a[u]-,)

          {

              dfs(u-,now+mi[u-]*i,now+mi[u-]*(i+)-,,s+(i==k));

              if(ans!=-INF) return;

          }

      }

 }

 int main()

 {

     //freopen("1.in","r",stdin);

     //freopen("1.out","w",stdout);

     int cas;

     scanf("%d",&cas);

     mi[]=;

     rep(i,,) mi[i]=mi[i-]*;

     while(cas--)

     {

         k=read(),n=read();

         ll n_=n;

         if(n==)

         {

             printf("0\n");

             continue;

         }

         len=;

         while(n)

         {

             a[++len]=n%;

             n/=;

         }

         ans=-INF;

         n=n_;

         dfs(len,,n,,);

         printf("%I64d\n",ans);

     }

     return ;

 }