#include <bits/stdc++.h>
using namespace std;
const int maxn = 110000;
int n, m, tt;
namespace Ninit {
void init() {
  scanf("%d%d", &n, &m);
  m = min(m, n / 2);
}
}  // namespace Ninit
namespace Nsolve {
inline long long calc(int m, int K) {
  int i;
  long long Fc = 0, C = 1, F = 0, S = (long long)K * m;
  for (i = 0; i <= K && F < S; ++i) {
    Fc += (F + C * i <= S ? C : (S - F) / i), F += C * i;
    if (Fc >= n) return Fc;
    C = C * (K - i) / (i + 1);
  }
  return Fc;
}
void solve() {
  int l = -1, r = n - 1, mid;
  for (; l + 1 < r; calc(m, mid) >= n ? r = mid : l = mid) mid = l + r >> 1;
  printf("%d\n", r);
}
}  // namespace Nsolve
int main() {
  for (cin >> tt; tt; --tt) {
    Ninit::init();
    Nsolve::solve();
  }
  return 0;
}
