#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define maxn 1000000000

using namespace std;

int T,n,m;

int qpow(int a,int b)
{
    int ans=1;
    while (b)
    {
        if (b&1) ans=ans*a;
        b>>=1;
        a=a*a;
    }
    return ans;
}

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        int ans=0;
        scanf("%d%d",&n,&m);
        m=min(30,m);
        while (n>0)
        {
            int p=qpow(2,m),c;
            if (n>=p)
            {
                c=n/p;
                n-=c*p;
                ans+=c;
            }
            m--;
        }
        printf("%d\n",ans);
    }
    return 0;
}