#include <bits/stdc++.h>
using namespace std;
long long tt, n, m;
bool solve(long long k) {
  long long lim = n - 1;
  if (!lim) return true;
  long long remain = m;
  long long choose1 = k, choose2 = 1;
  long long div1 = k - 1, div2 = k - 1, cnt = 1;
  while (lim && remain) {
    if (remain >= choose2) {
      if (lim >= choose1) {
        lim -= choose1;
        remain -= choose2;
        choose1 *= div1;
        choose1 /= (k - div1 + 1);
        div1--;
        choose2 *= div2;
        choose2 /= ((k - 1) - div2 + 1);
        div2--;
        if (!choose1 && lim) return false;
      } else
        return true;
    } else {
      long long total = 1LL * remain * k / cnt;
      if (lim <= total) return true;
      return false;
    }
    cnt++;
  }
  if (lim) return false;
  return true;
}
signed main() {
  cin >> tt;
  while (tt--) {
    cin >> n >> m;
    long long l = int(ceil(1.0 * log2(n)) - 1.0), r = n - 1;
    while (r - l > 1) {
      long long mid = (r + l) / 2;
      if (solve(mid))
        r = mid;
      else
        l = mid;
    }
    cout << r << "\n";
  }
}
