#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

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(ok(n,m,d)){
                res=min(res,m);
                r=m-1;
            }else{
                l=m+1;
            }
        }
        cout<<res<<endl;
    }
}