/*
ID: 1292871202
LANG: C++
*/
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <fstream>
#include <utility>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAX = 0x7fffffff;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const ll LMAX = 0x7fffffffffffffffLL;
const double eps = 1e-9;
const double pi=acos(-1.0);

const int maxn = 100000+5;
const int maxm = 100000+5;
const int mod = 1e9+7;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

ll solve(ll n,ll m)
{
    ll bi=0;
    while((1<<bi)<n)    bi++;
    if(m<bi)    bi=m;
    ll re=0;
    while(n)
    {
        re+=n/(1<<bi);
        n%=(1<<bi);
        bi--;
    }
    return re;
}
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //cin.sync_with_stdio(false);
    //cout.sync_with_stdio(false);
    int t;cin>>t;
    while(t--)
    {
        ll n,m;
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",solve(n,m));
    }
    return 0;
}