310477: CF1840B. Binary Cafe
Description
Once upon a time, Toma found himself in a binary cafe. It is a very popular and unusual place.
The cafe offers visitors $k$ different delicious desserts. The desserts are numbered from $0$ to $k-1$. The cost of the $i$-th dessert is $2^i$ coins, because it is a binary cafe! Toma is willing to spend no more than $n$ coins on tasting desserts. At the same time, he is not interested in buying any dessert more than once, because one is enough to evaluate the taste.
In how many different ways can he buy several desserts (possibly zero) for tasting?
InputThe first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.
Then follows $t$ lines, each of which describes one test case.
Each test case is given on a single line and consists of two integers $n$ and $k$ ($1 \le n, k \le 10^9$) — the number of coins Toma is willing to spend and the number of desserts in the binary cafe.
OutputOutput $t$ integers, the $i$-th of which should be equal to the answer for the $i$-th test case — the number of ways to buy desserts for tasting.
ExampleInput5 1 2 2 1 2 2 10 2 179 100Output
2 2 3 4 180Note
Variants for 1st sample: {}, {1}
Variants for 2nd sample: {}, {1}
Variants for 3rd sample: {}, {1}, {2}
Variants for 4th sample: {}, {1}, {2}, {1, 2}
Input
题意翻译
给定 $n$ 和 $k$，求有多少个 $k$ 位的二进制数（可以有前导零）小于等于 $n$。Output
Toma 发现自己在一个二进制咖啡馆里。咖啡馆提供 k 种不同的美味甜点，编号从 0 到 k-1。第 i 个甜点的价格是 2^i 枚硬币。Toma 愿意花费不超过 n 枚硬币来品尝甜点，且每种甜点只购买一次。问 Toma 有多少种不同的方式来购买甜点（可能一个都不买）。
输入输出数据格式：
输入：
第一行包含一个整数 t（1 ≤ t ≤ 1000），表示测试用例的数量。
接下来 t 行，每行描述一个测试用例，包含两个整数 n 和 k（1 ≤ n, k ≤ 10^9），分别表示 Toma 愿意花费的硬币数和咖啡馆里的甜点数量。
输出：
输出 t 个整数，第 i 个整数是第 i 个测试用例的答案，即购买甜点的不同方式数量。
示例：
输入：
5
1 2
2 1
2 2
10 2
179 100
输出：
2
2
3
4
180
注意：
第一个示例的变种：{}, {1}
第二个示例的变种：{}, {1}
第三个示例的变种：{}, {1}, {2}
第四个示例的变种：{}, {1}, {2}, {1, 2}题目大意： Toma 发现自己在一个二进制咖啡馆里。咖啡馆提供 k 种不同的美味甜点，编号从 0 到 k-1。第 i 个甜点的价格是 2^i 枚硬币。Toma 愿意花费不超过 n 枚硬币来品尝甜点，且每种甜点只购买一次。问 Toma 有多少种不同的方式来购买甜点（可能一个都不买）。 输入输出数据格式： 输入： 第一行包含一个整数 t（1 ≤ t ≤ 1000），表示测试用例的数量。 接下来 t 行，每行描述一个测试用例，包含两个整数 n 和 k（1 ≤ n, k ≤ 10^9），分别表示 Toma 愿意花费的硬币数和咖啡馆里的甜点数量。 输出： 输出 t 个整数，第 i 个整数是第 i 个测试用例的答案，即购买甜点的不同方式数量。 示例： 输入： 5 1 2 2 1 2 2 10 2 179 100 输出： 2 2 3 4 180 注意： 第一个示例的变种：{}, {1} 第二个示例的变种：{}, {1} 第三个示例的变种：{}, {1}, {2} 第四个示例的变种：{}, {1}, {2}, {1, 2}