#include <bits/stdc++.h>
using LL = long long;
const LL inf = 9e18;
LL mul(LL a, LL b) {
  if (a == 0 || b == 0) return a * b;
  if (a == inf || b == inf) return inf;
  if (inf / b <= a) return inf;
  return a * b;
}
LL divide(LL a, LL b) {
  if (a == inf) return inf;
  return a / b;
}
bool func(int m, int k, int n) {
  LL rest = m * 1LL * k;
  LL binom = 1;
  for (int i = 0; i <= k; ++i) {
    LL p = binom;
    if (i) p = std::min(p, rest / i);
    if (n <= p) return true;
    n -= p;
    rest -= p * i;
    binom = divide(mul(binom, k - i), i + 1);
    if (rest / (i + 1) < n) return false;
  }
  return false;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int cas;
  reader >> cas;
  while (cas--) {
    int n, m;
    reader >> n >> m;
    if (n == 1 || m == 1) {
      printf("%d\n", n - 1);
      continue;
    }
    int l = 1, r = n;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (func(m, mid, n))
        r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%d\n", r + 1);
  }
}
