#include <bits/stdc++.h>
using namespace std;
long long T, N, M;
bool Work(long long x) {
  long long i, tmp, mul = 1;
  long long rest = N, sum = x * M;
  if (N == 1)
    return true;
  else
    rest--;
  for (i = 1; i <= x && rest; i++) {
    mul = mul * (x - i + 1) / i;
    tmp = min(mul, rest);
    if (sum - tmp * i < 0) return false;
    sum -= tmp * i, rest -= tmp;
  }
  return (!rest);
}
int main() {
  long long i;
  long long l, r, mid;
  scanf("%I64d", &T);
  while (T--) {
    scanf("%I64d %I64d", &N, &M);
    l = 0, r = N;
    while (l <= r) {
      mid = (l + r) / 2;
      if (Work(mid))
        r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%I64d\n", l);
  }
  return 0;
}
