#include <bits/stdc++.h>
using namespace std;
int t;
int n, m;
int check(int x) {
  long long tot = 1ll * x * m;
  long long C = 1;
  long long num = 1;
  int k = 0;
  while (tot && k <= x) {
    k++;
    C = C * (x - k + 1) / k;
    if (tot - C * k >= 0)
      num += C, tot -= C * k;
    else
      num += tot / k, tot = 0;
    if (num > n) return 0;
  }
  if (num > n)
    return 0;
  else if (num < n)
    return 1;
  else if (num == n)
    return 2;
}
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d", &n, &m);
    int l = 0, r = n, ans = n;
    while (l <= r) {
      int mid = l + r >> 1;
      int nw = check(mid);
      if (nw == 0)
        ans = mid, r = mid - 1;
      else if (nw == 1)
        l = mid + 1;
      else {
        ans = mid;
        break;
      }
    }
    printf("%d\n", ans);
  }
}
