位运算

Problem Description

小丁最近对位运算很感兴趣，通过学习，他知道了按位与 $\otimes$，按位异或 $\oplus$，以及按位或 $\ominus$ 三种常见位运算。 按位与 $\otimes$：二进制下每一位做与，即 $0\otimes 0=0,0\otimes 1=0,1\otimes 0=0,1\otimes 1=1$。 按位异或 $\oplus$：二进制下每一位做异或，即 $0\oplus 0=0,0\oplus 1=1,1\oplus 0=1,1\oplus 1=0$​。 按位或 $\ominus$：二进制下每一位做或，即 $0\ominus 0=0,0\ominus 1=1,1\ominus 0=1,1\ominus 1=1$。 现在，对于一个在 $[0,2^k)$ 中的整数 $n$，小丁想要知道，有多少组也在 $[0,2^k)$ 中的整数 $a,b,c,d$，满足：

注意，运算符是从左往右依次顺序结合的，即可以认为原表达式为：

Input

本题单个测试点内包含多组测试数据。 第一行一个整数 $T(1\leq T\leq 10)$，表示数据组数。 对于每组数据，一行两个整数 $n,k$ $(1\leq k\leq 15,0\leq n<2^k)$。

Output

对于每组数据输出 $q$ 行，每行一个整数表示答案。

Sample Input

3
1 2
3 3
5 4

Sample Output

48
576
2304

Source

2024“钉耙编程”中国大学生算法设计超级联赛（1）