#include <iostream>
using namespace std;
typedef long long ll;
ll n,a,b,cnt;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        if(b==1){
            cout<<a-1<<endl;
        }
        else {
            cnt=0;
            ll L=1;
            while(a>1){
                a-=L;
                L*=b;
                cnt++;
            }
            cout<<cnt<<endl;
        }
    }
}