CF2240A.Another Popcount Problem

You are given two integers $n$ and $k$.

Your task is to construct a sequence $a$ consisting of $k$ non-negative integers $a_1, a_2, \ldots, a_k$ such that:

• $\sum_{i=1}^{k} a_i \le n$
• The total number of set bits, i.e., $\sum_{i=1}^{k} \operatorname{popcount}(a_i)$, is as large as possible.

You only need to output the maximum possible value of $\sum_{i=1}^{k} \operatorname{popcount}(a_i)$.

Here, $\operatorname{popcount}(x)$ denotes the number of $1$ bits in the binary representation of $x$. For example, $\operatorname{popcount}(6) = \operatorname{popcount}((110)_2) = 2$, and $\operatorname{popcount}(0) = 0$.

给你两个整数 $n$ 和 $k$。

你的任务是构造一个由 $k$ 个非负整数 $a_1, a_2, \ldots, a_k$ 组成的序列 $a$，满足：

• $\sum_{i=1}^{k} a_i \le n$
• 所有数的二进制表示中 $1$ 的总个数（即 $\sum_{i=1}^{k} \operatorname{popcount}(a_i)$）尽可能大。

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

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

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

Each of the next $t$ lines contains two integers $n$ and $k$ ($1 \le n, k \le 10^6$) — the maximum allowed sum of the sequence and the length of the sequence, respectively.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是测试用例的描述。

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

For each test case, output a single integer — the maximum possible value of $\sum_{i=1}^{k} \operatorname{popcount}(a_i)$.

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

In the first test case, $n=2$ and $k=1$. We can choose $a = [1]$ or $a = [2]$. In both cases, the sum of popcounts is $1$.

In the second test case, $n=3$ and $k=1$. We can choose $a = [3]$, since $(3)_2 = (11)_2$, $\operatorname{popcount}(3) = 2$.

In the third test case, $n=6$ and $k=2$. We can choose $a = [3, 3]$. The sum is $3 + 3 = 6 \le 6$, and the total popcount is $\operatorname{popcount}(3) + \operatorname{popcount}(3) = 2 + 2 = 4$.

在第一个测试用例中，$n=2$ 且 $k=1$。我们可以选择 $a = [1]$ 或 $a = [2]$。在这两种情况下，popcount 之和均为 $1$。

在第二个测试用例中，$n=3$ 且 $k=1$。我们可以选择 $a = [3]$，因为 $(3)_2 = (11)_2$，$\operatorname{popcount}(3) = 2$。

在第三个测试用例中，$n=6$ 且 $k=2$。我们可以选择 $a = [3, 3]$。其和为 $3 + 3 = 6 \le 6$，且总 popcount 为 $\operatorname{popcount}(3) + \operatorname{popcount}(3) = 2 + 2 = 4$。