#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int cal(int n){
    int ret=0;
    while(n){
        ret++;
        n&=n-1;
    }
    return ret;
}

int lowbit(int n){
    return n&(-n);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        int ans=0;
        while(cal(n)>k){
            ans+=lowbit(n);
            n+=lowbit(n);
        }
        printf("%d\n",ans);
    }
    return 0;
}