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

int main()
{
   
    int t;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            int ans=0;
            long long two=1;
            if(m>32)
                two<<=32;
            else two<<=m;
            while(two)
            {
                ans+=n/two;
                n=n%two;
                two>>=1;
            }
            printf("%d\n",ans);
        }

    }
    return 0;
}