#include <bits/stdc++.h>
using namespace std;
struct edge {
  int u, v;
  long long w;
};
long long MOD = 1000000007;
long long _MOD = 1000000009;
double EPS = 1e-10;
long long c[100][100];
long long C(long long n, long long k) {
  if (n < 100) return c[n][k];
  long long ans = 1;
  for (int i = 0; i < k; i++) ans *= n - i;
  for (int i = 1; i <= k; i++) ans /= i;
  return ans;
}
class NumberMagic {
 public:
  int theMin(int _N, int _M) {
    if (_N == 1) return 0;
    for (int i = 0; i < 100; i++) {
      c[i][0] = 1;
      for (int j = 1; j <= i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
    long long N = _N, M = _M;
    long long lb = 0, ub = N - 1;
    while (ub - lb > 1) {
      long long mid = (lb + ub) / 2;
      long long n = N, sum = 0;
      for (long long k = 0; k <= mid && n; k++) {
        long long unko = min(n, C(mid, k));
        n -= unko;
        sum += k * unko;
      }
      if (!n && sum <= mid * M)
        ub = mid;
      else
        lb = mid;
    }
    return ub;
  }
};
int main() {
  NumberMagic nm;
  int T;
  cin >> T;
  while (T--) {
    int N, M;
    cin >> N >> M;
    cout << nm.theMin(N, M) << endl;
  }
}
