#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    int t, ans, temp, n, m, max_w;
    scanf("%d", &t);//printf("%d", 1 <<0);
    for(int i = 1; i <= t; i++){
        scanf("%d%d", &n, &m);
        ans = 0;
        max_w = m;
        if(max_w > 30) max_w = 30; 
        for(int j = max_w; j >= 0; j--){
            temp = 1 << j;
            if(n >= temp){
                ans+=(n / temp);
                n-=(n/temp)*temp;
            }
        }
        printf("%d\n", ans);     
    }
    return 0;
}