#include <cstdio>

#include <cmath>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <map>



using namespace std;



typedef long long LL;


LL T,n,m,dq,now,ans;

int main()

{
    scanf("%I64d",&T);
    while (T--)
    {
        scanf("%I64d%I64d",&n,&m);
        dq=1;
        for (int i=1;i<=m;++i)
        {
            dq=dq*2;
            if (dq>=n) break;
        }
        ans=0;
        while (dq!=0)
        {
            now=n/dq;
            ans+=now;
            n-=dq*now;
            dq/=2;
        }
        printf("%I64d\n",ans);
    }

    return 0;

}