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


int main(){

    int q; cin >> q;
    for(int _ = 0; _ < q; ++_){
        long long n, k;
        cin >> n >> k;
        if(k == 1) {
            cout << n-1 << '\n';
        }else{
            int x = 0;
            while(pow(k, x) < n) ++x; 
            cout << x << '\n';
        }
        
    }
    return 0;
}