#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m;

int main() {
    int T;
    scanf( "%d", &T );
    while ( T -- ) {
        scanf( "%d%d", &n, &m );
        int ret = 0;
        m = min( m, 30 );
        for ( int i = m; i >= 0; i -- ) {
            ret += n / (1 << i);
            n %= (1 << i);
        }

        cout <<ret<<endl;
    }

    return 0;    
}