#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

ll k,n;

ll res=;

ll check()

{

    ll ans=;

    ll t=1ll;

    ll b=k-;

    while((t*k-)/b<n)t*=k,ans++;

   // if(t*k<0)puts(0);

    res=n-(t-)/b;

    if(res==)

    {

        res=;

        return ans;

    }

    if(res>t/k)res=;

    else res=;

    return ans;

}

int main()

{

    ll t;

    cin>>t;

    while(t--)

    {

        res=;

        cin>>k>>n;

        //else

        if(k==)cout<<n-<<'\n';

        //else if(k>1000000000)puts(0);

        else

        {

            ll x=check();

            if(res)cout<<x+x<<'\n';

            else cout<<x+(x-)<<'\n';

        }

    }

}

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

ll k,n;

ll res=;

ll check()

{

    ll ans=;

    ll t=; 

    while(t<n)n-=t,t*=k,ans++;

   //ll a=1;

   // if(t*k<0)puts(0);

    res=n;

    //cout<<res<<'\n';

    if(res==)

    {

        res=;

        return ans-;

    }

    if(res>t/k)res=;

    else res=;

    return ans;

}

int main()

{

    ll t;

    cin>>t;

    while(t--)

    {

        res=;

        cin>>k>>n;

        //else

        if(k==)cout<<n-<<'\n';

        //else if(k>1000000000)puts(0);

        else

        {

            ll x=check();

            if(res)cout<<x+x<<'\n';

            else cout<<x+(x-)<<'\n';

        }

    }

}