#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;
        if(K>1){
            double H=log(N*(K-1)+1)/log(K);
            cout << ceil(H)-1 << endl;
        }else cout << N-1 << endl;
    }
    return 0;
}