#include <bits/stdc++.h>
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    m = std::min(m, n / 2);
    int l = 0, r = n, ans;
    while (l <= r) {
      int mid = l + r >> 1;
      long long rem = (long long)mid * m, x = n, y = 1;
      for (int i = 0; i <= mid; i++) {
        rem -= i * std::min(x, y);
        x -= std::min(x, y);
        y = y * (mid - i) / (i + 1);
        if (rem < 0 || !x) break;
      }
      if (rem < 0 || x)
        l = mid + 1;
      else {
        ans = mid;
        r = mid - 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
