#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if (n==0){
            puts("0");
            continue;
        }
        if (m==0){
            printf("%d\n",n);
            continue;
        }
        if (m==1){
            printf("%d\n",(n>>1)+(n&1));
            continue;
        }
        int ans=0;
        for(int i=0;i<min(32,m)&&n>0;i++){
            ans+=n&1;
            n>>=1;
        }
        if (n) ans+=n;
        printf("%d\n",ans);
    }
    return 0;
}