#include <bits/stdc++.h>
using namespace std;
int t;
long long n, m;
bool check(long long k) {
  long long t = k * m, maxn = 1, c = 1;
  for (long long i = 1; i <= k; ++i) {
    c = c * (k - i + 1) / i;
    if (c * i > t) {
      maxn += t / i;
      break;
    }
    t -= c * i;
    maxn += c;
    if (maxn >= n) break;
  }
  return maxn >= n;
}
int main() {
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    cin >> n >> m;
    long long l(0), r(n - 1), mid;
    while (l < r) {
      mid = (l + r) >> 1;
      if (check(mid))
        r = mid;
      else
        l = mid + 1;
    }
    cout << l << endl;
  }
  return 0;
}
