CF1840B.Binary Cafe

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?

从前，托马来到了一家二进制咖啡馆。这是一家非常受欢迎且别具一格的场所。

咖啡馆为顾客提供 $k$ 种不同美味的甜点。这些甜点编号从 $0$ 到 $k-1$。第 $i$ 种甜点的价格为 $2^i$ 枚硬币，毕竟这是一家二进制咖啡馆！托马愿意花费至多 $n$ 枚硬币来品尝甜点。同时，他对同一种甜点不感兴趣购买超过一次，因为尝一次就足以品鉴其风味了。

那么，他有多少种不同的方式（可能为零种）来购买若干种甜点进行品尝？

The 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.

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

接下来是 $t$ 行，每行描述一个测试用例。

每个测试用例占一行，包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^9$）—— 分别表示 Toma 愿意花费的硬币数量以及二进制咖啡馆中甜点的数量。

Output $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.

输出 $t$ 个整数，其中第 $i$ 个整数应等于第 $i$ 个测试用例的答案——即购买甜点用于品尝的方案数。

Variants for 1st sample: {}, {1}

Variants for 2nd sample: {}, {1}

Variants for 3rd sample: {}, {1}, {2}

Variants for 4th sample: {}, {1}, {2}, {1, 2}

第1个样例的可能集合：{}, {1}

第2个样例的可能集合：{}, {1}

第3个样例的可能集合：{}, {1}, {2}

第4个样例的可能集合：{}, {1}, {2}, {1, 2}