#include <bits/stdc++.h>
using namespace std;
using namespace rel_ops;
const double PI = acos((double)-1);
int ts, ts2, ts3, ts4;
long long N, M;
long long gcd(long long x, long long y) {
  long long t;
  for (; y != 0;) {
    t = x % y;
    x = y;
    y = t;
  }
  return x;
}
double sqr(double x) { return x * x; }
template <class T>
void mn(T& x, T y) {
  x = min(x, y);
}
template <class T>
void mx(T& x, T y) {
  x = max(x, y);
}
int check(long long mid) {
  long long i, j, k, le, t1, t2, t3, t4, t5, t6, t7, t8, t9, t, nw,
      C = 1, resnum = N, rescolumn = M * mid;
  if (mid == 62) ts = 0;
  if (resnum) {
    resnum--;
  }
  if (rescolumn < 0) return 0;
  if (resnum == 0) return 1;
  for (i = 1; i <= mid; i++) {
    C = C * (mid - i + 1) / (i);
    t1 = min(resnum, C);
    resnum -= t1;
    rescolumn = rescolumn - t1 * i;
    if (rescolumn < 0) return 0;
    if (resnum == 0) return 1;
  }
  if (resnum == 0) return 1;
  return 0;
}
long long ans[10005];
int main() {
  long long i, j, k, le, t1, t2, t3, t4, t5, t6, t7, t8, t9, t, nw;
  int tt1, tt2, tt3, tt4;
  double u1, u2, u3, u4, u5, u6, u7, u8, u9;
  char c1, c2, c3;
  srand((unsigned)time(0));
  int T, T2;
  cin >> T;
  T2 = T;
  for (; T--;) {
    cin >> N >> M;
    M = min(M, N);
    if (M * 2 > N) M = N / 2;
    long long le, ri, mid;
    le = 0, ri = N;
    for (; le <= ri;) {
      mid = (le + ri) / 2;
      t1 = check(mid);
      if (t1)
        ri = mid - 1;
      else
        le = mid + 1;
    }
    ans[T2 - T] = le;
  }
  for (i = 1; i <= T2; i++) cout << ans[i] << endl;
  return 0;
}
