#include <cstdio>
#include <cstdlib>

int test, n, m;

int main() {
    scanf("%d", &test);
    while (test--) {
        scanf("%d %d", &n, &m);
        if (m > 30) {
            m = 30;
        }
        
        int ans = 0;
        for (int i = m; i >= 0; i--) {
            int x = (1 << i);
            ans += (n / x);
            n %= x;
        }
        
        printf("%d\n", ans);
    }
    
    return 0;
}