#include<bits/stdc++.h> #define int long long using namespace std; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } signed main() { cin.tie(0); ios::sync_with_stdio(false); int Q; cin>>Q; while(Q--){ int N,K; cin>>N>>K; if(K==1){ cout<<N-1<<endl; }else{ int x=1; for(int i=0;;i++){ N-=x; if(N<=0){ cout<<i<<endl; break; } x*=K; } } } return 0; }