#include <bits/stdc++.h>
using namespace std;
const long long inf = ~0ULL >> 3;
inline long long C(long long n, long long k) {
  long long re(1);
  for (int i = 1; i <= k; ++i) {
    re *= (n - i + 1);
    re /= i;
    if (re > inf || re < 0) return inf;
  }
  return re;
}
inline bool check(long long n, long long m, long long res) {
  long long sum(1), T(m * res);
  for (long long i = 1; T > 0 && i <= res && sum < n; ++i) {
    long long cr = C(res, i);
    if (cr != inf && cr * i > T)
      sum += T / i, T = 0;
    else
      sum += cr, T -= cr * i;
  }
  return sum >= n;
}
int main() {
  ios::sync_with_stdio(false);
  long long T, n, m;
  for (cin >> T; T--;) {
    cin >> n >> m;
    if (n == 1) {
      cout << 0 << endl;
      continue;
    }
    m = min(m, n);
    long long l(0), r(n), mi;
    while (l + 1 < r)
      if (check(n, m, mi = (l + r) / 2))
        r = mi;
      else
        l = mi;
    cout << r << endl;
  }
  return 0;
}
