题目描述

从前，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 翻译

样例

5
1 2
2 1
2 2
10 2
179 100

2
2
3
4
180