#include<iostream>
using namespace std;
int main(){
    int T, n, m,x,sum;
    cin >> T;
    while (T--){
        sum = 0;
        cin >> n>> m;
        int i=0;
        while (n>=(1<< i))
            i++;
        i--;
        if (i > m)
            i = m;
        while (n > 0){
            x = 1 << i;
            sum += n / x;
            n = n%x;
            i--;
        }
        cout << sum << endl;
    }
}