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

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