#include<iostream>

 #include<cstdlib>

 #include<stdio.h>

 #define ll long long

 using namespace std;

 ll a[],b[];

 int main()

 {

     int i,j,t,k;

     ll n,ans;

     scanf("%d",&t);

     while(t--){

         scanf("%d%lld",&k,&n);

         i=j=;

         a[]=b[]=;

         while(a[i]<n){

             i++;

             a[i]=b[i-]+;

             while(a[j+]*k<a[i]) j++;

             if(a[j]*k<a[i]) b[i]=b[j]+a[i];

             else b[i]=a[i];

         }

         if(a[i]==n) ans=(ll)n-i-;

         else ans=(ll)n-i;

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

     }

     return ;

 }