#include <bits/stdc++.h>
using namespace std;
int n, m, _c;
long long min(const long long x, const long long y) { return x < y ? x : y; }
long long C(const int x, const int y) {
  long long p = 1;
  for (int i = 1; i <= y; ++i) p = p * (x - i + 1) / i;
  return p;
}
bool ok(const long long x) {
  long long p = x * m, ans = 1, q;
  for (int i = 1; p >= i && i <= x; ++i) {
    q = min(C(x, i), p / i);
    ans += q;
    if (ans >= n) return 1;
    p -= q * i;
  }
  return 0;
}
int work() {
  scanf("%d%d", &n, &m);
  if (n == 1) return 0;
  int l = 0, r = n, mid;
  while (l + 1 < r) {
    mid = (l + r) >> 1;
    if (ok(mid))
      r = mid;
    else
      l = mid;
  }
  return r;
}
int main() {
  for (scanf("%d", &_c); _c--;) printf("%d\n", work());
  return 0;
}
