#include <bits/stdc++.h>
using namespace std;
int i, j, k, n, m, T, ch, l, r, mid;
void R(int &x) {
  x = 0;
  ch = getchar();
  while (ch < '0' || '9' < ch) ch = getchar();
  while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
void W(int x) {
  if (x >= 10) W(x / 10);
  putchar(x % 10 + '0');
}
bool check(int x) {
  if (n == 1) return 1;
  long long C = 1, tot = (long long)x * m, sum = 1, t;
  for (int i = 1; i <= x; i++) {
    if (tot < i) return 0;
    C = C * (x - i + 1) / i;
    if (C > tot / i)
      t = tot / i;
    else
      t = C;
    sum += t;
    tot -= t * i;
    if (sum >= n) return 1;
  }
  return 0;
}
int main() {
  R(T);
  while (T--) {
    R(n);
    R(m);
    l = 0;
    r = n;
    while (l < r) {
      mid = (l + r - 1) >> 1;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    W(l);
    puts("");
  }
}
