← 返回题目列表

Codeforces · 1840/B

B. 二元咖啡馆

中文机器翻译题面 查看原题

很久以前,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

5
1 2
2 1
2 2
10 2
179 100

输出 #1

2
2
3
4
180

注意

第一个示例的变体:{}、{1}

第二个示例的变体:{}、{1}

第三个示例的变体:{}、{1}、{2}

第 4 个示例的变体:{}、{1}、{2}、{1, 2}