#include <bits/stdc++.h>
int n, m, result;
bool ky(int K) {
  long long t, nown, p;
  double zh;
  int i;
  t = K;
  t = t * m;
  nown = 0;
  zh = 1;
  for (i = 1; i <= K; ++i) {
    if (t < i) break;
    if (t == 0) break;
    zh = zh * (K - i + 1.0);
    zh /= (i + 0.0);
    if (zh > t / i + 0.00001)
      p = t / i;
    else
      p = zh;
    nown += p;
    if (nown >= n - 1) return true;
    t -= i * p;
  }
  if (nown >= n - 1)
    return true;
  else
    return false;
}
void work() {
  int start, stop, mid;
  start = 1;
  stop = n - 1;
  while (start <= stop) {
    mid = (start + stop) / 2;
    if (ky(mid)) {
      result = mid;
      stop = mid - 1;
    } else
      start = mid + 1;
  }
}
int main() {
  int w, t;
  scanf("%d", &t);
  for (w = 1; w <= t; ++w) {
    scanf("%d%d", &n, &m);
    if (n == 1)
      printf("0\n");
    else if (n == 2)
      printf("1\n");
    else {
      work();
      printf("%d\n", result);
    }
  }
  return 0;
}
