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

Input

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.

Output

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

Note

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

Another Popcount Problem

Examples