### 问题描述 小然在一次冒险中发现了一个神秘的遗迹，遗迹中有 $N$ 个神秘符文石，每个符文石上都能镶嵌一定数量的魔法石。这些魔法石有个特性，就是它们的魔力值可以用二进制数表示，而魔力的强度取决于二进制表示中 '1' 的数量，我们记这个函数为 $f(X)$。 现在，小然需要在这 $N$ 个符文石上镶嵌魔法石，总的魔力值需要等于 $K$。每个符文石上的魔力值只能在 $0$ 到 $K$ 之间。小然希望镶嵌的魔法石可以使得所有符文石的魔力强度之和最大。 请你帮助小然计算出，他应该如何镶嵌魔法石，使得 $∑_{i=1}^{N} f(A_i)$ 最大。 ### 输入格式 第一行输入一个整数 $T$，表示测试用例的数量。 每个测试用例包含一行，包含两个整数 $N$ 和 $K$，分别表示符文石的数量和魔法石的总魔力值。 ### 输出格式 对于每个测试用例，输出一个整数，表示所有符文石的魔力强度之和的最大值。 ### 输入样例 ```text 2 1 7 3 6 ``` ### 输出样例 ```text 3 4 ``` ### 说明 测试用例 1：只有一个符文石，需要镶嵌的魔法石魔力值为 $7$。魔法石的魔力值 $7$ 的二进制表示为 $(111)$，所以魔力强度为 $3$。 测试用例 2：有三个符文石，需要镶嵌的魔法石总魔力值为 $6$。一个可能的方案是在第一个和第三个符文石上各镶嵌一个魔力值为 $3$ 的魔法石，这样每个魔力值为 $3$ 的魔法石的魔力强度为 $2$，所以总的魔力强度为 $4$。证明可知，魔力强度不会超过 $4$。 ### 评测数据范围 $1≤T≤10^4$。 $1≤N, K≤10^9$。