#include <bits/stdc++.h>
using namespace std;
long double optN(long long m, int k) {
  long double ret = 1;
  m *= k;
  long long nowC = k;
  for (int i = 1; i <= k; ++i) {
    if (m < nowC * i) {
      ret += m / i;
      return ret;
    }
    ret += nowC;
    m -= nowC * i;
    if (m / (i + 1.) / nowC <= (k - i) / (i + 1.)) return ret + m / (i + 1);
    nowC *= k - i;
    nowC /= (i + 1);
  }
  return ret;
};
int main() {
  int CASE;
  cin >> CASE;
  for (int TCASE = 1; TCASE <= CASE; ++TCASE) {
    long long n, m;
    cin >> n >> m;
    long long l = 0, r = (0x3f3f3f3f);
    while (l < r) {
      long long mid = l + r >> 1;
      if (optN(m, mid) >= n)
        r = mid;
      else
        l = mid + 1;
    }
    cout << l << endl;
  }
  return 0;
}
