#include <bits/stdc++.h>
using namespace std;
long long GCD(long long A, long long B) { return B ? GCD(B, A % B) : A; }
long long Min(long long UB, int N, int M) {
  M = min(M, N - M);
  long long S = 1;
  for (int i = 0; i < M; i++) {
    double Temp = S * (N - i) / (i + 1);
    if (Temp >= UB) return UB;
    long long T = N - i, K = GCD(S, i + 1);
    S = (S / K) * (T / ((i + 1) / K));
  }
  return S;
}
bool OK(int N, int M, int Ans) {
  long long Total = (long long)M * Ans;
  N--;
  for (int i = 1; N > 0 && i <= Ans && Total >= i; i++) {
    long long T = Min(Total / i, Ans, i);
    if (N <= T) return true;
    N -= T;
    Total -= i * T;
  }
  return N <= 0;
}
int main() {
  int Test;
  scanf("%d", &Test);
  while (Test--) {
    int N, M;
    scanf("%d%d", &N, &M);
    int Left = 0, Right = N - 1;
    while (Left < Right) {
      int Mid = (Left + Right) / 2;
      if (OK(N, M, Mid))
        Right = Mid;
      else
        Left = Mid + 1;
    }
    printf("%d\n", Left);
  }
  return 0;
}
