题目描述

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

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

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

输入格式

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

第一行一个整数 $T$（$1\le T\le 10$），表示数据组数。

对于每组数据，一行两个整数 $n,k$（$1\le k \le 15,0\le n \lt 2^k$）。

输出格式

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

输入样例

3
1 2
3 3
5 4

输出样例

48
576
2304