#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
  if (b == 0)
    return a;
  else
    return (gcd(b, a % b));
}
int com(int m, int n) {
  int a[16], b[16];
  int cs;
  long long e;
  n = min(n, m - n);
  if (n >= 20) return 2147483647;
  for (int i = 1; i <= n; i++) a[i] = m - i + 1, b[i] = i;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      cs = gcd(a[i], b[j]);
      a[i] /= cs;
      b[j] /= cs;
    }
  e = 1;
  for (int i = 1; i <= n; i++) {
    e = e * (long long)a[i];
    if (e > 2147483647) return 2147483647;
  }
  return int(e);
}
int solveit(int m, int s) {
  long long ans = 0, t = (long long)s * m, cs;
  for (int i = 0; i <= s; i++) {
    if (i == 0)
      cs = 1;
    else
      cs = t / i;
    if (cs == 0) break;
    cs = min(cs, (long long)com(s, i));
    t -= ((long long)cs * i);
    ans += cs;
    if (ans >= 2147483647) return 2147483647;
  }
  return ans;
}
int main() {
  int tt, n, m, left, right, mid, cs;
  scanf("%d", &tt);
  for (int gb = 1; gb <= tt; gb++) {
    scanf("%d %d", &n, &m);
    left = 0;
    right = n;
    while (left <= right) {
      mid = (left + right) / 2;
      cs = solveit(m, mid);
      if (cs >= n)
        right = mid - 1;
      else
        left = mid + 1;
    }
    printf("%d\n", left);
  }
  return 0;
}
