#include<bits/stdc++.h>

using namespace std;

// matrix multiplication
vector<vector<__int128>> matmul(vector<vector<__int128>> &a, vector<vector<__int128>> &b){
    int n = (int)a.size(), m = (int)a[0].size(), l = (int)b[0].size();
    vector<vector<__int128>> ret(n, vector<__int128>());
    for (int i = 0; i < n; i++){
        for (int j = 0; j < l; j++){
            __int128 ths = 0;
            for (int k = 0; k < m; k++){
                ths += a[i][k] * b[k][j];
            }
            ret[i].push_back(ths);
        }
    }

    return ret;
}

vector<vector<__int128>> matexp(vector<vector<__int128>> &mat, long long k){
    int n = (int)mat.size();
    if (k == 0){
        vector<vector<__int128>> id(n, vector<__int128>());
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                id[i].push_back(0);
            }
            id[i][i] = 1;
        }
        return id;
    }
    else if (k%2){
        vector<vector<__int128>> w = matexp(mat, k - 1);
        return matmul(w, mat);
    }
    else{
        vector<vector<__int128>> w = matexp(mat, k/2);
        return matmul(w, w);
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    long long x = 60, d = 300000;
    vector<vector<__int128>> dp(x + 1, vector<__int128>(d + 1, 0));
    vector<vector<__int128>> c(x + 1, vector<__int128>(x + 1, 0));
    c[0][0] = 1;
    for (int i = 0; i <= d; i++) dp[0][i] = 1;

    long long p = 1;
    for (int i = 1; i <= x; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= x; j++) {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }

        p *= 2;
        dp[i][1] = p;
        for (int j = 2; j <= d; j++) {
            for (int y = 0; y <= i; y++) {
                dp[i][j] += dp[i - y][j - 1] * c[i][y];
            }
        }
    }

    int t;
    cin >> t;

    while (t--) {
        long long n, dd;
        cin >> n >> dd;

        if (n == 1) {
            cout << 0 << '\n';
            continue;
        }

        if (dd <= d) {
            for (long long i = 1; i <= x; i++) {
                if (dp[i][dd] >= n) {
                    cout << i << '\n';
                    break;
                }
            }
        }
        else {
            vector<vector<__int128>> v = {{1}, {2}, {4}, {8}};
            vector<vector<__int128>> mat = {{1, 0, 0, 0}, {1, 1, 0, 0}, {1, 2, 1, 0}, {1, 3, 3, 1}};
            mat = matexp(mat, dd - 1);
            v = matmul(mat, v);

            if (v[1][0] >= n) {
                cout << 1 << '\n';
                continue;
            }
            if (v[2][0] >= n) {
                cout << 2 << '\n';
                continue;
            }
            if (v[3][0] >= n) {
                cout << 3 << '\n';
                continue;
            }

            cout << 4 << '\n';
        }
    }
    return 0;
}