#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;
            cnt=0;
            ll L=1;
            a--;
            if(b==1){
                cout<<a<<endl;
                continue;
            }
            while(a>0){
                L*=b;
                a-=L;
                cnt++;
            }
            cout<<cnt<<endl;
    }
}