#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<vector>
#include<ctype.h>
#include<algorithm>
using namespace std;
int rd(){
    int res=0,k=1; char c;
    while (c=getchar(),!isdigit(c)&&c!='-');
    if (c=='-') {k=-1; c=getchar();}
    do{
        res=(res<<3)+(res<<1)+(c^48);
    }while (c=getchar(),isdigit(c));
    return res*k;
}
int main(){
    int n;
    n=rd();
    while(n--){
        int a,b;
        a=rd();b=rd();
        int ans=0;
        for(int i=min(30,b);i>=0;i--){
            int k=1<<i;ans+=a/k;a%=k;
        }
        printf("%d\n",ans);
    }
    return 0;
}