#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

int main(){
    
    int t;
    ll n, m, ans, cnt;
    
    cin >> t;
    while(t--){
        cnt = ans = 0;
        scanf("%I64d %I64d", &n, &m);
        
        int x = n;
        while(x){
            x = x >> 1;
            cnt++;
        }
        
        if(m >= cnt){
            m = cnt;
        }
        
        for(int i = m; i >= 0; i--){
            while(n-(1<<i) >= 0){
                n -= (1<<i);
                ans++;
            }
        }
        printf("%I64d\n", ans);
    }
    
    return 0;
}