题目描述

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$ 步内赢的初始数的数量。

样例

7
4 1
4 2
4 3
4 4
4 5
16 5
16 1

3
2
0
0
0
4
15

样例说明

在第一个样例中，$a=2$、$a=3$、$a=4$ 满足条件，因为从 $a=1$ 一步可以变成 $0$，而对其它值可以证明最少需要 $2$ 步才行。

在第二个样例中，$a=3$ 和 $a=4$ 符合条件，因为对 $a=2$，Alice 可以通过 $2$ 步获胜。

在第三、四、五个样例中，没有符合条件的 $a$，因为对于 $a=3$ 和 $a=4$，Alice 至多三步内都能取胜。

由 ChatGPT 5 翻译

来源

Codeforces 2184D，英文题名 Unfair Game。