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

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$，满足：
$$a\otimes b\oplus c\ominus d=n$$

注意，运算符是从左往右依次顺序结合的，即可以认为原表达式为：
$$(((a\otimes b)\oplus c)\ominus d)=n$$

Input

本题单个测试点内包含多组测试数据。

第一行一个整数 $ T(1\leq T\leq 10) $，表示数据组数。

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

Output

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

3
1 2
3 3
5 4

48
576
2304