#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1<<18,INF=1<<30;

int main(){

    int Q;cin>>Q;
    while(Q){
        int N,K;cin>>N>>K;
        if(K==1){
            cout<<N-1<<endl;
        }else{
            ll now=1,sum=1;
            int ans=0;
            while(1){
                now*=K;
                sum+=now;
                ans++;
                if(sum>=N) break;
            }
            cout<<ans<<endl;
        }
        Q--;
    }
}