#include <iostream>
using namespace std;
typedef long long ll;

int main(){
    int Q;
    cin >> Q;
    for(int i=0;i<Q;i++){
        ll n,k;
        cin >> n >> k;
        ll node = 1;
        ll ans = 1;
        ll sum = 1;
        if(k==1){
            cout << n-1 << endl;
            continue;
        }
        while(sum<n){
            node *= k;
            sum += node;
            ans++;
        }
        cout << --ans << endl;
    }
}