/*
ID: jsnjhcb1
PROG: a
LANG: C++
*/
/*************************************************************************
    > File Name: a.cpp
    > Author: UCU
    > Mail: jsnjhcb@icloud.com
    > Created Time: 六  7/23 19:00:32 2016
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<string>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<iomanip>
#include<climits>
#include<fstream>
using namespace std;
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        int mm = 0;
        while((1<<mm) < n){
            ++mm;
        }
        m = min(mm,m);
        int ans = 0;
        for(int i=m;i>=0;--i){
            int tmp = n / (1<<i);
            ans += tmp;
            n %= (1 << i);
        }
        printf("%d\n",ans);
    }
    return 0;
}