Once upon a time, Toma found himself in a binary cafe. It is a very popular and unusual place.

The cafe offers visitors $k$ different delicious desserts. The desserts are numbered from $0$ to $k−1$. The cost of the $i$-th dessert is $2^i$ coins, because it is a binary cafe! Toma is willing to spend no more than $n$ coins on tasting desserts. At the same time, he is not interested in buying any dessert more than once, because one is enough to evaluate the taste.

In how many different ways can he buy several desserts (possibly zero) for tasting?

Upfront, this looks like a hard one: formally stated, we need to find the number of (potentially empty) subsets $S \in$ {$0, 1, \dots, k-1$} such that \(\displaystyle \sum_{i\in S}2^i \leq n.\) But when you start thinking in binary, this simplifies down to absolutely nothing! The cost when you choose the $i$ th object is $(c_i)_2 = 10000\dots 0$ where there are $i-1$ zeros. Thus, choosing a subset $S$ corresponds to activating the $j$ th bit from the right in the total cost. Eg. choose {$0, 2, 7$} and the cost is $2^0 + 2^2 + 2^7 = 128 + 4 + 1 = 133$ which corresponds exactly to $1000101$: the $0$ th, $2$ nd and $7$ th bits are on.

We, then, only need to find the number of ways we can choose places in the $k$ positions provided to us such that this combination is never greater than $n$. If the number of total places, $k$, is less than the number of bits in n, then no matter what we do, even if we choose all the elements we will still ensure total cost to be less than $n$. There are $2^k$ ways to do this, including the empty set.

On the other hand, if this is not the case, we have $n$ as our bottleneck. Here we note that if a bit is unset in $n$, it can never be selected when all the leftward set bits are selected. This gives rise to the following algorithm for this case:

• Initialise $sum = 0$.
• For each set bit in $n$, add $2^\text{number of bits to the right of the bit}$ to $sum$. This represents the number of choices when $b_i$ is turned off and all the bits to the left of $b_i$ that were set in $n$ are set.
• Finally, add $1$ to $sum$ to account for the total cost being exactly equal to $n$, which is always possible given $k > \lceil{\lg n}\rceil$.

Thus our final code is:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define F first
#define S second
#define rep(i, init, upper) for(size_t i=init; i<upper; i++)

int binpow(int a, int b){
    int result = 1;
    while(b){
        if(b & 1) result *= a;
        a *= a;
        b /= 2;
    }
    return result;
}

void solve(){
    int n, k;
    cin >> n >> k;
    int total_bits = CHAR_BIT * sizeof(int);
    int leading_zeros = __builtin_clz(n);
    int msb_pos = total_bits - leading_zeros - 1;

    if(k - 1 < msb_pos) cout << binpow(2, k) << "\n";
    else{
        bool is_set[total_bits];
        for(int i=0; i<total_bits; i++) is_set[i] = (n >> i) & 1;

        int sum = 1; // for when total price is exactly n
        int power2 = 1;
        for(int i=0; i<total_bits; i++){
            if(is_set[i]) sum += power2;
            power2 *= 2;
        }
        cout << sum << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    #ifndef ONLINE_JUDGE
        freopen("../input.txt", "r", stdin);
        freopen("../output.txt", "w", stdout);
    #endif
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}