#include <cstdio>
typedef long long LL;
int n, m;
int cnt_num(int x){
    return x == 0 ? 0 : cnt_num(x^(-x)&x) + 1;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        scanf("%d%d", &n, &m);
        if(m >= 31){
            printf("%d\n", cnt_num(n));
        }
        else if(n < 1 << (m+1)){
            printf("%d\n", cnt_num(n));
        }else{
            int cnt = 0;
            cnt += n / (1 << m);
            n %= (1 << m);
            cnt += cnt_num(n);
            printf("%d\n", cnt);
        }
    }
}