#include<stdio.h>
#include<math.h>

int main()
{
    int t, n, m, c;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        if (n == 0)
        {
            printf("0\n");
            continue;
        }
        int ans = 0;
        double a = log10(n), b = log10(2);
        int s = (int)(a/b)+1;
        m = m < s ? m : s;

        while (n > 0 && m >= 0)
        {
            c = pow(2, m);
            if (c <= n)
            {
                n -= c;
                ans++;
            }
            else
                m--;
        }
        printf("%d\n", ans);
    }
}