#include<stdio.h>

int main()
{
    int T,n,m,ans;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&m);
        for (ans=0;n && m;n>>=1,m--) ans+=(n & 1);
        ans+=n;
        printf("%d\n",ans);
    }
}