#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));

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

    int t;
    cin >> t;

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

        if (dd <= d) {
            for (long long i = 1; i <= x; i++) {
                if (dp[i][dd] >= n) {
                    cout << i << '\n';
                    break;
                }
            }
        }
        else {
            if (n <= 2) {
                cout << 1 << '\n';
                continue;
            }
            __int128 D = dd;
            __int128 ans_2 = 6 * D - 2;
            if (ans_2 >= n) {
                cout << 2 << '\n';
                continue;
            }

            vector<vector<__int128>> v = {{2}, {4}, {8}};
            vector<vector<__int128>> mat = {{1, 0, 0}, {3, 1, 0}, {0, 7, 1}};
            mat = matexp(mat, dd - 1);
            v = matmul(mat, v);
            if (v[2][0] >= n) {
                cout << 3 << '\n';
                continue;
            }

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