#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Min cost: viết T = sum c_i * 2^i (i=0..k-1), c_i >= 0, minimize sum c_i
ll f(ll T, ll k) {
    if (T == 0) return 0;
    int bl = 63 - __builtin_clzll(T) + 1;
    if (k >= bl) return __builtin_popcountll(T);
    ll shift = k - 1;
    ll top = T >> shift;
    ll bot = T & ((1LL << shift) - 1);
    return top + __builtin_popcountll(bot);
}
ll solve(ll n, ll k) {
    ll opt1 = f(n, k);
    if (n % 2 == 0) return min(opt1, f(n / 2, k));
    return opt1;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        ll n, k;
        cin >> n >> k;
        cout << solve(n, k) << "\n";
    }
    return 0;
}