#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define ld long double
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define rev(x) reverse(x.begin(), x.end())
#define fi first
#define se second
#define pb push_back
#define PI 3.14159265359
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}
#define sortpairbysec(x) sort(all(x), sortbysec)
bool sortcond(const pair<int,int> &a,const pair<int,int> &b){
    if (a.fi != b.fi){
        return a.fi < b.fi;
    } else {
        return a.se > b.se;
    }
}
struct myComp {
    constexpr bool operator()( pii const& a, pii const& b) const noexcept
    {
        if (a.first != b.first){
            return a.first < b.first;
        } else {
            return a.second > b.second;
        }
    }
};
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rng(ll lim) {
    uniform_int_distribution<ll> uid(0,lim-1);
    return uid(rang);
}

const int mod = 998244353;
const int N = 3e5, M = N;
const ll inf = 1e18;
//=======================
long long nCr(long long n, long long r){
    if (r > n) return 0;
    if (n-r < r) r = n-r;
    long long count = r;
    long long result = 1;
    while (count > 0){
        //result = m_mult(result, n);
        result = result * n;
        n--;
        count--;
    }
    long long num = 1;
    while (num <= r){
        //result = m_divide(result, num);
        result = result / num;
        num++;
    }
    return result;
}
//=======================
// & - bitwise AND; | - bitwise OR; ^ - bitwise XOR
// cout.precision(7);
// next_permutation(arr.begin(), arr.end());
// long long long long long long long long long long long long long long long long long long long long long long long long long long long
// priority_queue<int, vector<int>, greater<int>> a; (min heap)
// ll hash1 = hash<string>{}(to_string(1));
// always lower_bound
// __builtin_clz(n) count leading zeros

vl a;
ll n, m, k, q, d;

ll calc(ll sites, ll days){
    ll tot = 0;
    if (days == 1) return (1ll<<sites);
    for (int i = sites; i > 0; i--){
        int leftover = sites-i;
        if (leftover == 0){
            tot++;
        } else if (leftover == 1){
            tot += days*sites;
        } else {
            ll ret = calc(leftover, days-1);
            ll choose = nCr(sites, i);
            ld test = (ld)ret*(ld)choose;
            if (test >= (ld)n) return n;
            tot += ret*choose;
            if (tot >= n) return n;
        }
    }

    ld z = (ld)days*(ld)tot+(ld)1;
    if (z > (ld)n) return n;
    return days*tot+1;
}

void solve(int tc) {
    int i, j;
    cin >> n >> d;
    if (n == 1) {
        cout << 0 << "\n";
        return;
    }
    for (i = 1; i < 62; i++){
        if (calc(i, d) >= n){
            cout << i << "\n";
            return;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t = 1;
    cin >> t;
    int i;
    fo(i, t) {
        solve(i+1);
    }
    return 0;
}