A16491 | Unfair Game

Bob 厌倦了输给 Alice，为了保证自己不会再输，决定选择一个能确保自己获胜的游戏。Bob 从 $1$ 到 $n$ 中选了一个数，其中 $n = 2^d$，$d$ 是某个非负整数。起初，Alice 知道所选数字是否为偶数。

每一回合，Alice 可以选择将当前数字减半（只有当当前数字为偶数时可以执行），或者将当前数字减去 $1$。每次只有 Alice 执行操作。

操作后，Alice 会收到 Bob 的回复：要么是 $-1$，表示数字变为 $0$，Alice 获胜；要么是一个非负整数 $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>0$，这样的 $x$ 存在且唯一。

Bob 仍然担心 Alice 会获胜，因此游戏最多只能进行 $k$ 步。此外，Bob 想让自己尽可能多地赢，所以他希望游戏数尽量多。给定 $n$ 和 $k$，请计算使得 Alice 无法在不超过 $k$ 步内必胜的初始数的数量（即在 $1$ 到 $n$ 中，有多少个数 Alice 最优策略下无法在 $k$ 步内赢得游戏）。

第一行包含一个整数 $t$，表示测试用例数量，$1 \le t \le 10^4$。

每个测试用例包含一行，包含两个整数 $n$ 和 $k$，$1 \le n, k \le 10^9$，$n = 2^d$，$d$ 为某个非负整数。

对于每个测试用例，输出一行一个整数，表示对于 $1$ 到 $n$，Alice 最优情况下无法在最多 $k$ 步内赢的初始数的数量。