#include <iostream>
#include <cmath>
using namespace std;
int main(){
    long long Q,N,K;
    cin >> Q;
    for(int i=0;i<Q;i++){
        cin >> N >> K;
        int h=0;N--;
        while(N>0){
            N-=pow(K,h+1);
            h++;
        }
        cout << h << endl;
    }
    return 0;
}