#include<iostream>
#include<cstdio>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

using namespace std;

int n,m;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);int ans=0;
        rep(i,0,m){
            if(!n)break;
            if(n&1)++ans;
            n>>=1;
        }
        ans+=n<<1;
        printf("%d\n",ans);
    }
    return 0;
}