#include <bits/stdc++.h>

using namespace std;
using ll = long long;

bool ok(ll n, ll s, ll d) {
    if(n<=1) return true;
    if(d==0||s==0) return false;
    if(n<=(d+1)) return true;
    return ok((n+s)/(s+1),s-1,d-1);
}

bool ok2(ll n, ll s, ll d) {
    bool res=false;
    for(ll i=0;i<=s;i++){
        res|=ok(n-((ll)1<<i)+1,s-i,d);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    ll t;
    cin>>t;
    while(t--){
        ll n, d;
        cin>>n>>d;
        ll l=0, r=61;
        ll res=n;
        while(l<=r){
            ll m=(l+r)/2;
            if(ok2(n,m,d)){
                res=min(res,m);
                r=m-1;
            }else{
                l=m+1;
            }
        }
        cout<<res<<endl;
    }
}