#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>
#include <ctime>
//#include <unordered_map>
//#define ls (x<<1)
//#define rs (x<<1|1)
//#define mid ((lt[x].l+lt[x].r)/2)
//#define ID(x, y) ((x)*m+(y))
#define CHECK(x, y) ((x)>=0 && (x)<n && (y)>=0 && (y)<m)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF=0x3f3f3f3f;
void Open()
{
    #ifndef ONLINE_JUDGE
        freopen("/home/qingping/in.txt","r",stdin);
//        freopen("D:/my.txt","w",stdout);
    #endif // ONLINE_JUDGE
}
int two[1111];
int main(){
//    Open();
    two[0] = 1;
    int st;
    for(st = 1; two[st-1] < 1000000000; st++)
        two[st] = two[st-1]*2;
//    cout<<st<<endl;
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        int sum = 0;
        for(int i = min(m, st-1); i >= 0; i--)
        {
            sum += n / two[i];
            n %= two[i];
        }
        printf("%d\n", sum);
    }
    return 0;
}