#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const long long INF = 1e18 + 1e6 + 228;

long long safe_add(long long a, long long b) {
  return min(INF, a + b);
}

long long safe_mul(long long a, long long b) {
  if (a == 0 || b == 0)
    return 0;
  if (b > INF / a)
    return INF;
  return min(INF, a * b);
}

vector<vector<long long>> mul(const vector<vector<long long>>& A, const vector<vector<long long>>& B) {
  vector<vector<long long>> ans(A.size(), vector<long long>(B[0].size()));
  for (int i = 0; i < A.size(); ++i) {
    for (int j = 0; j < A[0].size(); ++j) {
      for (int k = 0; k < B[0].size(); ++k)
        ans[i][k] = safe_add(ans[i][k], safe_mul(A[i][j], B[j][k]));
    }
  }
  return ans;
}

vector<vector<long long>> bin_pow(vector<vector<long long>> A, long long n) {
  vector<vector<long long>> ans(A.size(), vector<long long>(A.size()));
  for (int i = 0; i < A.size(); ++i)
    ans[i][i] = 1;
  while (n) {
    if (n & 1) {
      auto tmp = mul(ans, A);
      swap(tmp, ans);
    }
    n >>= 1;
    auto tmp = mul(A, A);
    swap(tmp, A);
  }
  return ans;
}

const int MX = 70;

long long C[MX][MX];

void solve() {
  long long n;
  long long d;
  cin >> n >> d;
  long long k = 1;
  while (true) {
    vector<vector<long long>> matrix(k + 1, vector<long long>(k + 1));
    for (int i = 0; i <= k; ++i) {
      long long cur = 1;
      for (int j = i; j <= k; ++j) {
        matrix[i][j] = C[j][i];
      }
    }

    vector<vector<long long>> dp(1, vector<long long>(k + 1));
    dp[0][0] = 1;
    auto tmp = mul(dp, bin_pow(matrix, d + 1));
    long long kek = tmp[0][k];
    if (kek >= n)
      break;
    ++k;
  }
  cout << k << '\n';
}


int main() {
#ifdef DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#else
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
#endif

  for (int n = 0; n < MX; ++n) {
    C[n][0] = 1;
    for (int k = 1; k <= n; ++k)
      C[n][k] = safe_add(C[n - 1][k - 1], C[n - 1][k]);
  }

  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}