#include <bits/stdc++.h>
using namespace std;
int n, m;
int qpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) ret = 1LL * ret * x % 1000000007;
    k >>= 1;
    x = 1LL * x * x % 1000000007;
  }
  return ret;
}
bool check(int k) {
  if (n == 1) return 1;
  long long sum = 1, t = 1LL * k * m;
  double c = 1;
  long long s = 1;
  for (int i = 1; i <= k; ++i) {
    long long x = t / i, y = 1000000007;
    if (x == 0) return 0;
    c = c * (k - i + 1) / i;
    s = s * (k - i + 1) % 1000000007 * qpow(i, 1000000007 - 2) % 1000000007;
    if (c < 1000000007) y = s;
    x = min(x, y);
    sum += x;
    if (sum >= n) return 1;
    t -= x * i;
  }
  return 0;
}
int main() {
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    scanf("%d%d", &n, &m);
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) / 2;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    printf("%d\n", l);
  }
  return 0;
}
