#include <iostream>
using namespace std;


int main(){
    long long n,m;
    cin >> n;
    while(cin >> n >> m){
        if( m >= 30 ){
            cout << __builtin_popcount(n) << endl;
        }else{
            long long a = (1<<m);
            long long ans = n / (1<<m);
            ans += __builtin_popcount(n%(1<<m));
            cout << ans << endl;
        }
    }
    
}