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

typedef long long ll;

ll p[40];

void init() {
    p[0] = 1;
    for (int i = 1; i <= 32; i++)
        p[i] = p[i - 1] * 2;
}

int main() {
    //freopen("in.txt", "r", stdin);
    init();
    int T;
    cin >> T;
    while (T--) {
        ll n, m;
        scanf("%I64d%I64d", &n, &m);
        m = min(m, (ll)32);
        ll sum = 0;
        for (int i = m; i >= 0; i--) {
            sum += n / p[i];
            n %= p[i];
        }
        printf("%I64d\n", sum);
    }
    return 0;
}