CF2184D.Unfair Game

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:

1. $a$ is divisible by $2^x$.
2. $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.

鲍勃厌倦了输给爱丽丝，为了确保自己不再输，他决定选择一个自己必胜的游戏。鲍勃从 $1$ 到 $n$ 之间想好了一个数，其中已知 $n = 2^d$（$d$ 为某个非负整数）。初始时，爱丽丝知道该数是偶数还是奇数。

在一次操作中，爱丽丝可以执行以下两种操作之一：将当前数减半，或减 $1$。她仅当当前数为偶数时才能执行减半操作。只有爱丽丝进行操作。

每次操作后，鲍勃会向爱丽丝返回一个响应：要么是 $-1$，表示该数已变为 $0$，爱丽丝获胜；要么是一个非负整数 $x$。若记当前数为 $a$，则 $x$ 同时满足以下两个条件：

1. $a$ 能被 $2^x$ 整除；
2. $a$ 不能被 $2^{x+1}$ 整除。

例如，若 $a=5$，则 $x=0$，因为 $5$ 可被 $2^0 = 1$ 整除，但不可被 $2^1 = 2$ 整除；若 $a=12$，则 $x=2$，因为 $12$ 可被 $2^2 = 4$ 整除，但不可被 $2^3 = 8$ 整除。

可以证明：对任意正整数 $a$，均存在唯一满足上述条件的 $x$。

鲍勃仍担心爱丽丝获胜，因此游戏最多进行 $k$ 步。此外，鲍勃希望最大化自己的胜率，即尽可能多地进行游戏。给定 $n$ 和 $k$，请计算在 $1$ 到 $n$ 的初始数字中，有多少个数使得爱丽丝即使采取最优策略，也无法在至多 $k$ 步内获胜。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例仅一行，包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^9$）—— 分别为所选数字的上限以及 Alice 的最大移动次数。保证 $n = 2^d$，其中 $d$ 为某个非负整数。

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.

对于每个测试用例，输出从 $1$ 到 $n$ 中满足以下条件的整数个数：Alice 以最优策略进行游戏时，无法在至多 $k$ 步内获胜。

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.

在第一个样例中，$a=2$、$a=3$ 和 $a=4$ 是合适的，因为从 $a=1$ 出发可在 $1$ 步操作内到达 $0$，而对其他取值，可以证明至少需要 $2$ 步操作。

在第二个样例中，$a=3$ 和 $a=4$ 是合适的，因为当 $a=2$ 时，Alice 可在 $2$ 步操作内获胜。

在第三、第四和第五个样例中，不存在合适的 $a$，因为当 $a=3$ 和 $a=4$ 时，Alice 均可在 $3$ 步操作内获胜。