#include <bits/stdc++.h>
using namespace std;
const long long inv = numeric_limits<long long>::max();
int T;
int n, m;
bool possible(int k) {
  long long res = 0, rem = ((long long)(m)) * ((long long)(k));
  long long dres, drem;
  dres = 1;
  drem = 0;
  for (int i = 0; i <= k; ++i) {
    if (rem >= drem) {
      res += dres;
      rem -= drem;
    } else {
      res += (rem / ((long long)(i)));
      return (res >= (long long)(n));
    }
    if (i < k) {
      if (dres > (inv) / ((long long)(k - i)))
        drem = inv;
      else {
        dres *= ((long long)(k - i));
        dres /= ((long long)(i + 1));
        drem = dres * ((long long)(i + 1));
      }
    }
  }
  return (res >= (long long)(n));
}
int binsrc(int l, int r) {
  if (l + 1 == r)
    return r;
  else {
    int mid = (l + r) / 2;
    if (possible(mid))
      return binsrc(l, mid);
    else
      return binsrc(mid, r);
  }
}
int main() {
  scanf("%d", &T);
  for (int z = 0; z < T; ++z) {
    scanf("%d%d", &n, &m);
    if (n == 1) {
      printf("0\n");
      continue;
    }
    if (possible(1))
      printf("1\n");
    else
      printf("%d\n", binsrc(1, n - 1));
  }
  return 0;
}
