#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <string>  
#include <string.h>       
#include <vector>    
#include <queue>    
#include <stack>
#include <map>

using namespace std;

#define ll long long

int main(){
    
    
    
    int t;
    cin>>t;
    
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        
        int ans = 0;
        m = min(29,m);
        for(int i=m;i>=0;i--){
            ll cur = 1LL<<i;
            ll tmp = n/cur;
            //cout<<"tmp = "<<tmp<<endl;
            n -= tmp*cur;
            ans += tmp;
        }
        cout<<ans<<endl;
    }
    
    
    return 0;
}