#include #define rep(i,n) for(int i=0;i<(n);++i) using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); int q; cin >> q; vector n(q); vector k(q); rep(i, q) cin >> n[i] >> k[i]; vector ans(q); rep(i, q) { ll res = 1; ll sol = n[i]; while (1) { sol -= res; res *= k[i]; if (sol > 0) ans[i]++; else break; } if (k[i] == 1) ans[i] = n[i] - 1; } rep(i, q) cout << ans[i] << endl; }