该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定两个整数 $(n, k)$，其中 $(0 \leq n < 2^k)$。求有多少组有序整数对 $(a, b, c, d)$ 使得 $(0 \leq a, b, c, d < 2^k)$ 且 $(((a \otimes b) \oplus c) \oslash d = n)$。其中 $(\otimes)$ 为按位与运算，$(\oplus)$ 为按位异或运算，$(\oslash)$ 为按位或运算
这些运算的定义如下：

按位与运算：二进制下的每一位做与运算。例如，$(12 \otimes 10 = 1100_2 \otimes 1010_2 = 1000_2 = 8)$
按位异或运算：二进制下的每一位做异或运算。例如，$(12 \oplus 10 = 1100_2 \oplus 1010_2 = 0110_2 = 6)$
按位或运算：二进制下的每一位做或运算。例如，$(12 \oslash 10 = 1100_2 \oslash 1010_2 = 1110_2 = 14)$

输入格式

第一行一个整数 $T (1 \leq T \leq 10)$，表示数据组数 对于每组数据，一行两个整数 $n, k(1 \leq k \leq 15, 0 \leq n < 2^k)$。

输出格式

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

样例

3
1 2
3 3
5 4

48
576
2304