#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }


void MAIN() {
    int N, M;
    scanf("%d%d", &N, &M);
    int ans = 0;
    for (int i=min(30, M); i>=0 && N; i--) {
    ans += N / (1 << i);
    N %= (1 << i);
    }
    printf("%d\n", ans);
}
int main() {
    int tt;
    scanf("%d", &tt);
    REP (i, tt) MAIN();


    return 0;
}