#include <bits/stdc++.h>
using namespace std;

int main(){
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        long long N, K;
        cin >> N >> K;
        if(K == 1)cout << N - 1 << endl;
        else{
            long long node = 1;
            long long chil = 1;
            long long depth = 0;
            while(node < N){
                chil *= K;
                node += chil;
                depth++;
            }
            cout << depth << endl;
        }
    }
    return 0;
}