题目背景

题目描述

定义 $f(x)=x\oplus (x+2^k)$，其中 $\oplus$ 是二进制下的异或运算。

给定两个整数 $n,k$。

请你输出 $f(0)+f(1)+f(2)+\cdots+f(n)$ 的值。

有关异或运算的知识，您可以在 OI Wiki 相关界面查询到。

输入格式

本题有多组数据。

第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行两个整数 $n,k$。

输出格式

输出有 $T$ 行，对每个询问输出答案。

样例

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

样例 1 解释

对于第一组样例，$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$，因此答案为 $1+3+1+7=12$。

数据范围

对于 $20\%$ 数据，$n,T \leq 5000$。

对于另外 $20\%$ 数据，$n \leq 10^5$。

对于另外 $30\%$ 数据，$k = 0$。

对于 $100\%$ 数据，$1\le T \leq 10^5$，$0\le n < 2^{29}$，$0\le k \leq 29$。