#include <bits/stdc++.h>
using namespace std;
const long long maxa = 1000000010;
long long calc(long long m, long long d) {
  long long lim = m * d, ent = 1, cnt = 0;
  long long i;
  for (i = 0; i <= d; ++i) {
    if ((i && ent > lim / i + 10) || ent * i > lim) break;
    lim -= ent * i;
    cnt += ent;
    if (cnt > maxa) return maxa;
    ent = ent * (d - i) / (i + 1);
  }
  if (i <= d) cnt += lim / i;
  return cnt;
}
long long solve(long long n, long long m) {
  long long l = -1, r = maxa;
  while (r - l > 1) {
    long long d = (l + r) / 2;
    if (calc(m, d) >= n)
      r = d;
    else
      l = d;
  }
  return r;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  long long t;
  cin >> t;
  for (long long i = 0; i < t; ++i) {
    long long n, m;
    cin >> n >> m;
    cout << solve(n, m) << '\n';
  }
}
