#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long qpow(long long x, long long tms) {
  long long tmp = 1;
  while (tms) {
    if (tms & 1) tmp = tmp * x % mod;
    tms >>= 1;
    x = x * x % mod;
  }
  return tmp;
}
int n, m, T;
bool chk(int k) {
  if (n == 1) return 1;
  long long sum = 1, t = (long long)k * m;
  double C = 1;
  long long s = 1;
  for (int i = 1; i <= k; ++i) {
    long long x = t / i, y = mod;
    if (x == 0) return 0;
    C = C * (k - i + 1) / i;
    s = s * (k - i + 1) % mod * qpow(i, mod - 2) % mod;
    if (C < mod) y = s;
    x = min(x, y);
    sum += x;
    if (sum >= n) return 1;
    t -= x * i;
  }
  return 0;
}
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (chk(mid))
        r = mid;
      else
        l = mid + 1;
    }
    printf("%d\n", l);
  }
}
