#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int a[100010], b[100010];
int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        int n, m;
        scanf("%d%d", &n, &m);
        int r = 0;
        while (n){
            
            if (m == 0){
                r += n;
                n = 0;
            }
            m--;
            r += n % 2;
            n /= 2;
        }
        printf("%d\n", r);
    }
#ifdef local
    DonotReturn();
#endif
}