#include<iostream>
using namespace std;

int main(){
    // freopen("input","r",stdin);
    // freopen("output","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int sum=0;
        int k=0,r=1;
        while(r*2<=n){
            k++;r*=2;
        }
        if(k<=m){
            while(n){
                sum+=n/r;
                n%=r;
                r/=2;
            }
        }else{
            r=1;
            for(int i=0;i<m;i++){
                r*=2;
            }
            while(n){
                sum+=n/r;
                n%=r;
                r/=2;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}