#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, ans, T;
int main() {
    scanf("%d", &T);
    while (T--) {
        ans = 0;
        scanf("%d%d", &n, &m);
        if (m > 30) m = 30;
        for (int i = (1 << m); i; i >>= 1) {
            ans += (n / i);
            n %= i;
        }
        printf("%d\n", ans);
    }
}