#include <iostream>

using namespace std;

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