#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e6, lg = 31;
long long C[maxn][lg];
long long getC(long long n, long long k) {
  if (n < maxn) return C[n][k];
  long double ans = 1;
  for (long long i = 0; i < k; i++) {
    if (ans >= 1e16) break;
    ans *= n - i;
    ans /= i + 1;
  }
  return ans;
}
bool check(long long n, long long m, long long t) {
  long long d = min((long long)ceil(log2(n)) + 1, t);
  n--;
  for (long long i = 1; i <= d; i++) {
    if (m < getC(t - 1, i - 1)) {
      n -= t * m / i;
      m = 0;
    } else {
      m -= getC(t - 1, i - 1);
      n -= getC(t, i);
    }
    if (n <= 0) return 1;
    if (m == 0) return 0;
  }
  return n <= 0;
}
long long bs(long long n, long long m) {
  long long l = ceil(log2(n)) - 1, r = n;
  while (r > l + 1) {
    long long t = (l + r) / 2;
    if (check(n, m, t))
      r = t;
    else
      l = t;
  }
  return r;
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  C[0][0] = 1;
  for (long long i = 1; i < maxn; i++) {
    C[i][0] = 1;
    for (long long j = 1; j < min(i + 1, lg); j++)
      C[i][j] = min(C[i - 1][j - 1] + C[i - 1][j], (long long)1e18);
  }
  long long t;
  cin >> t;
  while (t--) {
    long long n, m;
    cin >> n >> m;
    cout << bs(n, m) << '\n';
  }
}
