#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
long long d, n;
bool can(ll y){
    ll divfact = y*2;
    int cnt = 0;
    ll ni = n;
    while (ni > 1){
        ni = (ni-1)/divfact+1;
        cnt++;
    }
    if (cnt <= d) {
        return true;
    }
    return false;
}

void solve(){

    cin >> n >> d;
    if (n == 1){
        cout << 0 << "\n";
        return;
    }
    ll l = 0;
    ll r = 1e18;
    while (r - l > 1){
        ll m = (l+r)/2;
        if (can(m)){
            r = m;
        } else {
            l = m;
        }
    }
    cout << r << "\n";

}

int main(){

    int t = 1;
    cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
}