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). 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. For each test case, output a single integer — the maximum possible value of (\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).