#include <bits/stdc++.h>
using namespace std;
class NumberMagic {
 public:
  int theMin(int, int);
};
long long C(long long a, long long b) {
  long long ans = 1;
  for (long long i = 1; i <= b; i++) ans *= (a - i + 1), ans /= i;
  return ans;
}
long long make(long long x, long long N) {
  long long ans = 0;
  for (long long i = 0; i <= x; i++) {
    long long cur;
    if (x >= 1000000LL && i >= 3)
      cur = N + 1;
    else
      cur = C(x, i);
    if (N <= cur * i) {
      ans += N / i;
      return ans;
    }
    ans += cur;
    N -= cur * i;
  }
  return ans;
}
int NumberMagic::theMin(int N, int M) {
  int L = 1, R = 1000000000, ans = 0;
  while (L <= R) {
    long long mid = (long long)(((long long)L + (long long)R) / 2);
    long long minT = make(mid, (long long)M * mid);
    if ((long long)N <= minT)
      ans = (int)mid, R = mid - 1;
    else
      L = mid + 1;
  }
  return ans;
}
int main() {
  NumberMagic a;
  int T, n, m;
  for (cin >> T; T; T--) {
    cin >> n >> m;
    if (n == 1)
      cout << 0 << endl;
    else
      cout << a.theMin(n, m) << endl;
  }
  return 0;
}
