#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[111111];
bool ok(int k) {
  int nn = n;
  long long total = 1LL * m * k;
  int cur = 1;
  for (int i = 0; i <= k; ++i) {
    if (total < i) return false;
    int p = nn;
    if (1LL * p * i > total) p = total / i;
    int q;
    if (i <= k / 2) {
      c[i] = cur;
      if (1LL * cur * (k - i) >= 1LL * n * (i + 1))
        cur = n;
      else
        cur = 1LL * cur * (k - i) / (i + 1);
      q = c[i];
    } else {
      q = c[k - i];
    }
    if (q < p) p = q;
    total -= 1LL * p * i;
    if (p >= nn) return true;
    nn -= p;
  }
  return false;
}
int main() {
  int tests;
  scanf("%d", &tests);
  while (tests--) {
    scanf("%d%d", &n, &m);
    int l = -1, r = n - 1;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (ok(mid))
        r = mid;
      else
        l = mid;
    }
    printf("%d\n", r);
  }
  return 0;
}
