// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  ll q;
  cin >> q;
  while(q--) {
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    ll now = 1;
    ll leaf = 1;
    if(k == 1) {
      cout << n - 1 << "\n";
    } else {
      while(now < n) now += leaf * k, leaf *= k, ans++;
      cout << ans << "\n";
    }
  }
  return 0;
}