#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int ans = 0;
        int n, m;
        scanf("%d%d", &n, &m);
        m = min(m, 30);
        while(m--)
        {
            ans += n & 1;
            n >>= 1;
        }
        ans += n;
        printf("%d\n", ans);
    }
    return 0;
}