#include <cstdio>
#define rpt(i,l,r) for(int i=l;i<=r;i++)
#define rpd(i,r,l) for(int i=r;i>=l;i--)
int T,n,m,ans;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&m,&n);
        if(n>29) n=29;
        ans=0;
        rpd(i,n,0) ans+=m/(1<<i),m%=(1<<i);
        printf("%d\n",ans);
    }
}