#include<bits/stdc++.h> #define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i) #define rep(i,a,b) for(int i=int(a);i<int(b);++i) #define All(x) (x).begin(),(x).end() using namespace std; typedef long long ll; int main(){ int Q;cin>>Q; REP(q,Q){ ll N,K;cin>>N>>K; ll ans=0,tmp=1; if(K==1){ ans=N-1; } else{ while(N>0){ N-=tmp*K; tmp*=K; ans++; } } cout<<ans<<endl; } }