#include <bits/stdc++.h>
long long min(long long a, long long b) { return a < b ? a : b; }
bool check(int n, int m, int mid) {
  long long res = (long long)m * mid, z = 1;
  for (int i = 0; i <= mid && n; i++) {
    long long k = min(z, n);
    z = z * (mid - i) / (i + 1);
    res -= k * i;
    n -= k;
  }
  return res >= 0 && !n;
}
int cal(int n, int m) {
  int l = 0, r = n - 1, mid;
  m = min(m, n / 2);
  while (l < r) {
    mid = (l + r) / 2;
    if (check(n, m, mid))
      r = mid;
    else
      l = mid + 1;
  }
  return r;
}
int main() {
  int t, n, m;
  scanf("%d", &t);
  while (t--) scanf("%d%d", &n, &m), printf("%d\n", cal(n, m));
  return 0;
}
