#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
  int t;
  cin >> t;
  for (; t--;) {
    cin >> n >> m;
    if (n == 1) {
      cout << 0 << endl;
      continue;
    }
    int ansl = 0, ansr = n, ans = (ansl + ansr) / 2;
    for (; ansl < ansr; ans = (ansl + ansr) / 2) {
      int tmp = n;
      long long C = 1, all = 0;
      for (int i = 0; i <= ans; ++i) {
        all += (long long)min((long long)tmp, C) * i;
        tmp -= min((long long)tmp, C);
        if (!tmp) break;
        C *= ans - i;
        C /= i + 1;
      }
      if (!tmp)
        if (all > (long long)m * ans)
          ansl = ans + 1;
        else
          ansr = ans;
      else
        ansl = ans + 1;
    }
    cout << ans << endl;
  }
  return 0;
}
