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


#define N 100200
#define M 200020
#define mod 1000000007
#define LL long long
#define ls (i << 1)
#define rs (ls | 1)
#define md (ll + rr >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs

int main() {
    int cas;
    scanf("%d", &cas);
    while(cas--) {
        int n, m;
        scanf("%d%d", &n, &m);
        int d = 1 << (min(m, 30));
        int ans = 0;
        while(n) {
            ans += n / d;
            n -= n / d * d;
            d /= 2;
        }
        printf("%d\n", ans);
    }
    return 0;
}