#include <bits/stdc++.h>
using namespace std;
bool debug;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;
bool ok(long long n, long long m, long long dni) {
  long long s = 0;
  long long nt = 1;
  long long i = 1;
  long long dupuj = 0;
  while (nt && s + nt <= n) {
    if (debug) printf("%lld %lld\n", s, nt);
    dupuj += (i - 1) * nt;
    s += nt;
    nt = nt * (dni + 1 - i) / i;
    ++i;
    if (nt == 0LL && s < n) return false;
  }
  dupuj += (i - 1) * (n - s);
  return dupuj <= dni * m;
}
int ttt() {
  long long n, m;
  scanf("%lld%lld", &n, &m);
  if (n == 1LL) return 0;
  if (m == 1LL) return (int)n - 1;
  long long low = 1, high = n;
  while (low < high) {
    long long med = (low + high) / 2;
    if (ok(n, m, med))
      high = med;
    else
      low = med + 1;
  }
  return (int)low;
}
int main(int argc, char *argv[]) {
  debug = argc > 1;
  int z;
  scanf("%d", &z);
  while (z--) printf("%d\n", ttt());
  return 0;
}
