#include<stdio.h>
int main(){
    int t;
    int n,m,k;
    scanf("%d",&t);
    while(t--){
        int i,ans=0;
        scanf("%d%d",&n,&m);
        if(m>=31)   m=31;
        for(i=m;i>=0;i--){
            k=0;
            if(i==0)    k=n;
            if(n>=(1<<i)&&i!=0){
                k=n/(1<<i);
                n=n%(1<<i);
            }
            ans+=k;
            if(n==0)    break;
        }
        printf("%d\n",ans);
    }
    return 0;
}