#include <bits/stdc++.h>
int n, m, answer;
bool check(int t) {
  long long int i, K = 0;
  long long int rest, ncr, p;
  rest = (long long int)t * m;
  ncr = 1;
  K = 1;
  for (i = 1; i <= t; i++) {
    ncr *= ((long long int)t) - i + 1;
    ncr /= i;
    if (rest / i > ncr)
      p = ncr;
    else
      p = (rest / i);
    K += p;
    rest -= p * i;
    if (rest < 0) return false;
    if (K >= n) return true;
  }
  if (rest < 0) return false;
  if (K >= n) return true;
  return false;
}
int main(void) {
  int test, f, l, mid;
  scanf("%d", &test);
  for (; test >= 1; test--) {
    scanf("%d %d", &n, &m);
    f = 0, l = n;
    for (;;) {
      mid = (f + l) / 2;
      if (check(mid)) {
        l = mid - 1;
        answer = mid;
      } else
        f = mid + 1;
      if (f > l) break;
    }
    printf("%d\n", answer);
  }
  return false;
}
