#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T, n, m;

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