#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
#define ll long long

int main() {
    int t;  
    scanf("%d", &t);
    while(t--) {
        ll n, m;  
        scanf("%I64d%I64d", &n, &m);
        if(n == 0) {
            puts("0");
            continue;
        }
        int ans = 0;
        ll now;
        ll x = n;
        int tmp = 0;
        while((1 << tmp) <= n) {
            tmp++;
        }
        if(m < 1ll * 31)
            now = min(1ll << m, 1ll << tmp);
        else now = 1ll << 31;
        while(x) {
            ans += x / now;
            x %= now;
            now /= 2;
        }
        printf("%d\n", ans);
    }
    return 0;
}