#include <bits/stdc++.h>
using namespace std;
int n, m;
long long C(long long n, long long m) {
  long double tmp = 1.0;
  for (long long i = 0; i < m; i++) tmp *= (n - i) / (i + 1.0);
  if (tmp > 1.2e9) return (long long)1.2e9;
  m = min(m, n - m);
  long long ret = 1;
  for (int i = (0); i <= (m - 1); i++) ret = ret * (n - i) / (i + 1);
  return ret;
}
long long solve(long long m, long long k) {
  long long ret = 1, left = k * m;
  for (int i = (1); i <= (k); i++) {
    if (left < i || ret > 1.1e9) break;
    long long x = min(left / i, C(k, i));
    ret += x;
    left -= x * i;
  }
  return ret;
}
int main() {
  int Q;
  cin >> Q;
  while (Q--) {
    cin >> n >> m;
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) / 2;
      if (solve(m, mid) >= n)
        r = mid;
      else
        l = mid + 1;
    }
    cout << l << endl;
  }
  return 0;
}
