#include <bits/stdc++.h>
int T;
int N, M;
long long gcd(long long a, long long b) {
  while (b != 0) {
    long long t = a % b;
    a = b;
    b = t;
  }
  return a;
}
long long C(long long n, long long k) {
  long long res = 1;
  long long den = 1;
  int i;
  for (i = 1; i <= k; ++i) {
    long long r = n - i + 1;
    long long d = i;
    long long g = gcd(r, d);
    if (g > 1) {
      r /= g;
      d /= g;
    }
    res *= r;
    den *= d;
    g = gcd(res, den);
    if (g > 1) {
      res /= g;
      den /= g;
    }
  }
  return res;
}
int main() {
  int tt;
  scanf("%d", &T);
  for (tt = 1; tt <= T; ++tt) {
    scanf("%d %d", &N, &M);
    if (M == 1) {
      printf("%d\n", N - 1);
      continue;
    }
    int sol = N - 1;
    int lo = 0;
    int hi = N - 2;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      long long n = 0;
      int i;
      long long t = ((long long)mid) * M;
      for (i = 0; i <= mid && i <= t; ++i) {
        long long p = ((i > 0) ? t / i : N);
        long long r = C(mid, i);
        if (p > r) p = r;
        n += p;
        t -= p * i;
        if (n >= N) break;
      }
      if (n >= N) {
        sol = mid;
        hi = mid - 1;
      } else
        lo = mid + 1;
    }
    printf("%d\n", sol);
  }
  return 0;
}
