题目描述

给定两个正整数 $n$ 和 $k$。

你的任务是构造一个由 $k$ 个非负整数组成的序列 $a_1, a_2, \dots, a_k$，使得满足以下条件：

• $\sum_{i=1}^k a_i \le n$；
• 序列中所有元素的二进制置位（即 $1$）的数量之和，也就是 $\sum_{i=1}^k \text{popcount}(a_i)$，尽可能大。

你只需要输出 $\sum_{i=1}^k \text{popcount}(a_i)$ 可能的最大值。

$\text{popcount}(x)$ 表示数字 $x$ 在二进制表示中 $1$ 的个数。例如，$\text{popcount}(6) = \text{popcount}((110)_2) = 2$，而 $\text{popcount}(0) = 0$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 测试用例的数量。

接下来 $t$ 行，每行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 10^6$）—— 分别表示序列元素之和的最大允许值，以及序列的长度。

输出格式

对于每个测试用例，输出一行一个整数，表示 $\sum_{i=1}^k \text{popcount}(a_i)$ 可能的最大值。

样例输入 1

6
2 1
3 1
6 2
14142 137205
1000000 100
1000000 1000000

样例输出 1

1
2
4
14142
1322
1000000

说明

样例解释

• 在第一个测试用例中，$n=2, k=1$。我们可以选择 $a = [1]$ 或 $a = [2]$，这两种情况下 $\text{popcount}$ 的总和均为 $1$。
• 在第二个测试用例中，$n=3, k=1$。我们可以选择 $a = [3]$，因为 $(3)_{10} = (11)_2$，所以 $\text{popcount}(3) = 2$。
• 在第三个测试用例中，$n=6, k=2$。我们可以选择 $a = [3, 3]$。总和为 $3+3=6 \le 6$，且总的 $\text{popcount}$ 为 $\text{popcount}(3) + \text{popcount}(3) = 2 + 2 = 4$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^3$。
• 对于每个测试用例，保证 $1 \le n, k \le 10^6$。
• 保证所有的输入数值均为整数。