#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>

using namespace std;

long long  T,n,m,now,ans;
int main()
{
    
    cin >> T;
    for (;T>0;T--)
    {
        cin >> n >> m;
        now=1;
        for (int i=1;i<=m;i++)
        {
            now=now*2;
            if (now*2>n) break;
        }
        ans=0;
        for (;now>0;now/=2)
        {
         ans=ans+n/now;
         n=n % now;
        }
        cout << ans << endl;
    }
    return 0;
}