CF1840B Binary Cafe

从前，Toma 来到了一家二进制咖啡馆。这是一家非常受欢迎且与众不同的地方。 咖啡馆为顾客提供 $k$ 种不同的美味甜点。甜点编号从 $0$ 到 $k-1$。第 $i$ 种甜点的价格为 $2^i$ 个硬币，因为这是一家二进制咖啡馆！Toma 愿意花费不超过 $n$ 个硬币来品尝甜点。同时，他对每种甜点只想品尝一次，因为一次就足以评价味道。 他有多少种不同的方式可以购买若干（也可以不买）甜点来品尝？

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 接下来有 $t$ 行，每行描述一个测试用例。 每个测试用例包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^9$），分别表示 Toma 愿意花费的硬币数量和二进制咖啡馆中的甜点种类数。

输出 $t$ 个整数，第 $i$ 个整数表示第 $i$ 个测试用例的答案，即购买甜点的方案数。

第 1 个样例的方案：$\{\}$，$\{1\}$。 第 2 个样例的方案：$\{\}$，$\{1\}$。 第 3 个样例的方案：$\{\}$，$\{1\}$，$\{2\}$。 第 4 个样例的方案：$\{\}$，$\{1\}$，$\{2\}$，$\{1, 2\}$。 由 ChatGPT 4.1 翻译