#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


ll n, d;

inline bool check(ll p) {
    __int128_t C = 1, now = 0, f = 1;
    for(ll t = 0; t <= p; t++) {
        if(f >= n || C >= n) return 1;
        now += f * C;
        if(now >= n) return 1;
        C = C * (d - t) / (t + 1);
        f *= p - t;
    }
    return now >= n;
}

inline void Solve() {
    cin >> n >> d;
    ll l = 1, r = n, ans = n;
    while(l <= r) {
        ll mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

signed main() {
    int t;
    cin >> t;
    for(; t--; ) {
        Solve();
    }
    return 0;
}