#include <bits/stdc++.h>
using namespace std;
void setIO(string a) {
  string in = a + ".in", out = a + ".out";
  freopen(in.c_str(), "r", stdin);
  freopen(out.c_str(), "w", stdout);
}
unsigned long long n, m;
inline int ck(unsigned long long x) {
  if (x <= 30 && n > (1LL << x)) return 0;
  unsigned long long Ans = 1, C = 1, t = x * m;
  for (int i = (1); i <= (x); i++) {
    unsigned long long add = (t / i);
    if (!add) break;
    C = 1ll * C * (x - i + 1) / (i);
    add = min(add, C);
    Ans += add;
    t -= add * i;
    if (!t) break;
  }
  return Ans >= n;
}
int T;
int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%I64u%I64u", &n, &m);
    unsigned long long l = 0, r = n;
    while (l + 1 < r) {
      int md = (l + r) >> 1;
      if (ck(md))
        r = md;
      else
        l = md;
    }
    ck(6);
    if (ck(l)) r = l;
    printf("%I64u\n", r);
  }
  return 0;
}
