#include <bits/stdc++.h>
using namespace std;
int n, m;
bool pan(int k) {
  long long C = 1, num = 1, t = (long long)k * m;
  for (int i = 1; i <= k && t; i++) {
    C = C * (k - i + 1) / i;
    if (t / i > C) {
      num += C;
      t -= C * i;
    } else
      num += t / i, t = 0;
    if (num >= n) return true;
  }
  return num >= n;
}
int main() {
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    scanf("%d%d", &n, &m);
    int g = 0, h = n, ans = 0;
    while (g <= h) {
      int mid = (g + h) / 2;
      if (pan(mid)) {
        ans = mid;
        h = mid - 1;
      } else
        g = mid + 1;
    }
    printf("%d\n", ans);
  }
  return 0;
}
