#include <bits/stdc++.h>
using LL = long long;
bool func(int m, int k, int n) {
  if (k <= 30 && (1 << k) < n) return false;
  LL binom = 1;
  LL sum = 0;
  int cnt = 0;
  for (int i = 0; i <= k; ++i) {
    int val = std::min<LL>(n - cnt, binom);
    cnt += val;
    sum += val * 1LL * i;
    if (cnt == n) break;
    binom = binom * (k - i) / (i + 1);
  }
  return sum <= m * 1LL * k;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::istream& reader = std::cin;
  int cas;
  reader >> cas;
  while (cas--) {
    int n, m;
    reader >> n >> m;
    if (n == 1 || m == 1) {
      printf("%d\n", n - 1);
      continue;
    }
    int l = 1, r = n;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (func(m, mid, n))
        r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%d\n", r + 1);
  }
}
