Bob is tired of losing to Alice and, to ensure he doesn't lose again, decided to choose a game in which he is guaranteed to win. Bob has thought of a number from $$$1$$$ to $$$n$$$, where it is known that $$$n = 2^d$$$ for some non-negative integer $$$d$$$. Initially, Alice knows whether the chosen number is even or not.

In one move, Alice can either halve the number or subtract $$$1$$$. Alice can only halve the number if the current number is even. Only Alice takes turns.

After her move, Alice receives a response from Bob: either $$$-1$$$, which means the number has become $$$0$$$ and Alice has won, or a non-negative integer $$$x$$$. If we denote the current number as $$$a$$$, then for $$$x$$$ the following conditions hold simultaneously:

$$$a$$$ is divisible by $$$2^x$$$.
$$$a$$$ is not divisible by $$$2^{x+1}$$$.

For example, if $$$a=5$$$, then $$$x=0$$$, since $$$5$$$ is divisible by $$$2^0=1$$$ and not divisible by $$$2^1=2$$$, and if $$$a=12$$$, then $$$x=2$$$, since $$$12$$$ is divisible by $$$2^2=4$$$ and not divisible by $$$2^3=8$$$.

It can be shown that for any integer $$$a \gt 0$$$, there exists a unique such $$$x$$$.

Bob is still afraid that Alice will win, so the game will have no more than $$$k$$$ moves. Additionally, Bob wants to maximize his chances of winning, so he wants to play as many games as possible. Given $$$n$$$ and $$$k$$$, calculate the number of initial numbers from $$$1$$$ to $$$n$$$ such that Alice, playing optimally, cannot win in no more than $$$k$$$ moves.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

The only line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ $$$(1 \le n, k \le 10^9)$$$ — the limit on the chosen number and the maximum number of Alice's moves, respectively. It is guaranteed that $$$n = 2^d$$$ for some non-negative integer $$$d$$$.

Output

For each test case, output the number of integers from $$$1$$$ to $$$n$$$ such that Alice, playing optimally, cannot win in at most $$$k$$$ moves.

Note

In the first sample, $$$a=2$$$, $$$a=3$$$, and $$$a=4$$$ are suitable because from $$$a=1$$$ one can reach $$$0$$$ in $$$1$$$ operation, while for the other values, it can be shown that at least $$$2$$$ operations are required.

In the second sample, $$$a=3$$$ and $$$a=4$$$ are suitable because for $$$a=2$$$, Alice can win in $$$2$$$ operations.

In the third, fourth, and fifth samples, there are no suitable $$$a$$$, because for $$$a=3$$$ and $$$a=4$$$, Alice can win in $$$3$$$ operations.

Unfair Game

Examples