Description

Define $f(x) = x \oplus (x + 2^k)$, where $\oplus$ denotes the bitwise XOR operation.

Given two integers $n$ and $k$, compute the value of $f(0) + f(1) + f(2) + \cdots + f(n)$.

For knowledge about XOR operations, you may refer to the Wikipedia Page.

Input Format

Multiple test cases.

The first line contains a positive integer $T$ indicating the number of test cases.

Each of the next $T$ lines contains two integers $n$ and $k$.

Output Format

Output $T$ lines, each containing the answer for the corresponding query.

9
3 0
15 0
9 4
3 6
17 28
9 16
8 23
15 11
4 11

12
80
160
256
4831838208
655360
75497472
32768
10240

Hint

Explanation #1

Sample 1 Explanation:

For the first test case:

• $f(0) = 0 \oplus (0 + 2^0) = 1$
• $f(1) = 1 \oplus (1 + 2^0) = 3$
• $f(2) = 2 \oplus (2 + 2^0) = 1$
• $f(3) = 3 \oplus (3 + 2^0) = 7$

Thus, the answer is $1 + 3 + 1 + 7 = 12$.

Constraints

• 20% of data: $n, T \leq 5000$
• Additional 20% of data: $n \leq 10^5$
• Additional 30% of data: $k = 0$
• 100% of data: $1 \leq T \leq 10^5$, $0 \leq n < 2^{29}$, $0 \leq k \leq 29$

Translated by DeepSeek R1