#include <bits/stdc++.h>
using namespace std;
template <class T>
void pv(T a, T b) {
  for (T i = a; i != b; ++i) cout << *i << " ";
  cout << endl;
}
template <class T>
void chmin(T &t, const T &f) {
  if (t > f) t = f;
}
template <class T>
void chmax(T &t, const T &f) {
  if (t < f) t = f;
}
int in() {
  int x;
  scanf("%d", &x);
  return x;
}
long long N, M;
bool check(long long k) {
  if (k <= 30) {
    if (N > 1LL << k) {
      return false;
    }
  }
  long long comb = 1;
  long long n = N;
  long long ask = 0;
  for (int r = 0; n > 0; ++r) {
    long long tmp = min(comb, n);
    n -= tmp;
    ask += r * tmp;
    comb = comb * (k - r) / (1 + r);
  }
  return (ask <= M * k);
}
int main() {
  for (int TC = in(); TC--;) {
    N = in();
    M = in();
    long long lo = -1, ho = N - 1;
    for (; lo + 1 < ho;) {
      long long mo = (lo + ho) / 2;
      (check(mo) ? ho : lo) = mo;
    }
    cout << ho << endl;
  }
  return 0;
}
