#include <bits/stdc++.h>
using namespace std;
int test, n, m;
long long combine(int n, int m) {
  long long ret = 1;
  for (int i = 0; i < m; i++) ret = ret * (n - i) / (i + 1);
  return ret;
}
int check(int x) {
  long long ones = (long long)x * m, nn = 1;
  for (int k = 1; k <= x && ones >= k && nn < n; k++) {
    long long com = combine(x, k), num = min(com, ones / k);
    nn += num;
    ones -= num * k;
  }
  return nn >= n;
}
int main() {
  cin >> test;
  while (test--) {
    cin >> n >> m;
    int ll = 0, rr = n - 1, mid;
    while (ll < rr) {
      mid = (ll + rr) >> 1;
      if (check(mid))
        rr = mid;
      else
        ll = mid + 1;
    }
    cout << ll << endl;
  }
  return 0;
}
