#include <bits/stdc++.h>
using namespace std;
int n;
int m;
long long check(long long k) {
  long long h = k * m;
  long long res = 1;
  int i = 1;
  long long newk = 1;
  while (h > 0 && res < n && i <= m && i <= k) {
    if (newk < n) {
      newk *= (k - i + 1);
      newk /= i;
      if (newk > n) newk = n;
    }
    long long tmp = newk;
    if (i > 0) tmp = min(tmp, h / i);
    h -= tmp * i;
    res += tmp;
    i++;
    if (res >= n) return res;
  }
  return res;
}
int main() {
  int tt;
  scanf("%d", &tt);
  for (int it = 0; it < tt; it++) {
    scanf("%d%d", &n, &m);
    long long l = -1, r = 0x7fffffff;
    while (r - l > 1) {
      long long s = (l + r) / 2;
      if (check(s) >= n)
        r = s;
      else
        l = s;
    }
    printf("%I64d\n", r);
  }
  return 0;
}
