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