#include <cstdio>
#include <cmath>
int T, n, m, s, x;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d", &n, &m);
        if (m > 30)
            printf("%d\n", __builtin_popcount(n));
        else
        {
            s = 0;
            do
                s += x = n / (1 << m), n -= x * (1 << m);
            while (m--);
            printf("%d\n", s);
        }
    }
    return 0;
}