#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;

int T, n, m;

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        int p = -1, ans = 0;
        while(n > 0 && ++p <= m)
        {
            if(n % 2 == 1) ans += 1;
            n /= 2;
        }
        int u = 1;
        while(n > 0)
        {
            u *= 2;
            if(n % 2 == 1) ans += u;
            n /= 2;
        }
        printf("%d\n", ans);
    }
}