#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    const int maxn = 61;
    ll C[maxn + 1][maxn + 1];
    C[0][0] = 1;
    for (int n = 1; n <= maxn; ++n) {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k)
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
    }

    vector<vector<ll>> dp(61, vector<ll>(31623, 0));

    for(int i = 0; i <= 31622; i++)
        dp[0][i] = 1;

    for(int i = 1; i <= 60; i++){
        dp[i][0] = 1; 

        for(int j = 1; j <= 31622; j++)
            for(int k = 0; k <= i; k++)
                dp[i][j] += C[i][k] * dp[i - k][j - 1];
    }

    int t;
    cin >> t;
    int cnt = 0;

    while(t--){
        ll n, d;
        cin >> n >> d;

        if(d <= 31622){
            for(int i = 0; i <= 60; i++){
                if(dp[i][d] >= n){
                    cout << i << "\n";
                    break;
                }
            }
        }else{
            if(1 >= n){
                cout << "0\n";
            }else if(d + 1 >= n){
                cout << "1\n";
            }else if(d >= 999999999ll || (d + 1) * (d + 1) >= n){
                cout << "2\n";
            }else if(d >= 1000000ll || d + 1 + 3 * d * (d + 1) / 2 + d * (2 * d + 1) * (d + 1) / 2 >= n){
                cout << "3\n";
            }else{
                cout << "4\n";
            }
        }
    }
}