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

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    long long tes;

    cin >> tes;

    while(tes--){
        long long n, d;
        cin >> n >> d;

        if(n == 1){
            cout << 0;
            return 0;
        }

        if(d >= 61){
            cout << 1;
            return 0;
        }

        long long x = (1LL << d), nam = x;
        long long ans = 1;

        while(nam < n){
            long long q = n / x;
            if(n % x) q++;
            if(nam >= q){
                ans++;
                break;
            }

            ans++;
            nam *= x;
        }

        cout << ans << endl;
    }
    return 0;
}