#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int calc( long long x ) {
    int ret = 0;
    for( int i = 0 ; i < 30 ; i++ )
        ret += (x>>i)&1;
    return ret;
}

int main() {
    int t , n , m;
    scanf( "%d" , &t );
    while( t-- ) {
        scanf( "%d%d" , &n , &m );
        if( m > 30 ) {
            cout << calc( n ) << endl;
        }
        else {
            cout << (n>>m)+calc( n&((1<<m)-1) ) << endl;
        }
    }
    return 0;
}