#include <bits/stdc++.h>
using namespace std;
unsigned long long C(int n, int m) {
  if (m > n) return 0;
  if (m == n || !m) return 1;
  if (m < (n >> 1)) m = n - m;
  unsigned long long ret = 1;
  int x = 1;
  for (int t = m + 1; t <= n; t++) {
    ret = ret * t;
    for (; ret % x == 0 && x <= (n - m); x++) ret /= x;
  }
  return ret;
}
const long long LLINF = 0x3f3f3f3f3f3f3f3fLL;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, M;
    scanf("%d%d", &N, &M);
    int lb = 1, rb = N - 1, ans = 0;
    while (lb <= rb) {
      int mid = (lb + rb) >> 1;
      long long lim = (long long)mid * M;
      long long cur = 0, sum = 0;
      for (int i = 1; i <= mid; i++) {
        long long t = C(mid, i);
        if (cur + (long long)t * i > lim) {
          long long delta = (lim - cur) / i;
          cur = LLINF;
          sum += delta;
        } else {
          sum += t;
          cur += (long long)t * i;
        }
        if (sum >= N - 1 || cur > lim) break;
      }
      if (sum >= N - 1)
        rb = mid - 1, ans = mid;
      else
        lb = mid + 1;
    }
    cout << ans << endl;
  }
}
