#include <cstring>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string>
using namespace std;

const int N = 50010;
int main () {
//    freopen ("in.txt", "r", stdin);
    int T, n, m;
    cin >> T;
    while (T--) {
        scanf ("%d%d", &n, &m);
        m = min (m, 30);
        int r = 0;
        for (int i = 0; i < m; i++) if (n & (1 << i)) r++;
        r += n >> m;
        printf ("%d\n", r);
    }
}