#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>

#define ll long long
#define INF 1000000000
using namespace std;
const int maxn=1000009;
int a[maxn],dp[maxn];
int n,i,j;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        int x=1,ans=0,cnt=0;
        while(n>=2*x){
            if(cnt>=m)
                break;
            x*=2;
            cnt++;
        }
        while(n!=0){
            int t=n/x;
            ans+=t;
            n-=t*x;
            x/=2;
        }
        printf("%d\n",ans);
    }
    return 0;
}