小丁最近对位运算很感兴趣，通过学习，他知道了按位与 $⊗$，按位异或 $⊕$，以及按位或 $⊖$ 三种常见位运算。

按位与 $⊗$：二进制下每一位做与，即 $0⊗0=0,0⊗1=0,1⊗0=0,1⊗1=1$。

按位异或 $⊕$：二进制下每一位做异或，即 $0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0$。

按位或 $⊖$：二进制下每一位做或，即 $0⊖0=0,0⊖1=1,1⊖0=1,1⊖1=1$。

现在，对于一个在 $[0,2k)$ 中的整数 $n$，小丁想要知道，有多少组也在 $[0,2k)$ 中的整数 $a,b,c,d$，满足：
$a⊗b⊕c⊖d=n$

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

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

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

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

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