对于一个 $n \times m$ 的二进制矩阵 $A$，如果对于所有 $1 \le i \le n, 1 \le j \le m$，第 $i$ 行所有元素的异或和与第 $j$ 列所有元素的异或和之异或值等于 $A_{i,j}$（注意 $A_{i,j}$ 被计算了两次），则称该矩阵为“好矩阵”。

形式化地，好矩阵的定义为： $\forall i, j \ (1 \le i \le n, 1 \le j \le m), \left(\bigoplus_{k=1}^m A_{i,k}\right) \oplus \left(\bigoplus_{k=1}^n A_{k,j}\right) = A_{i,j}$

给定 $n$ 和 $m$，你需要求出好矩阵的数量。由于答案可能非常大，请输出结果对 $998\,244\,353$ 取模后的值。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \times 10^5$)，表示测试用例的数量。 对于每个测试用例， 仅一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^{18}$)，表示矩阵的行数和列数。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示好矩阵的数量对 $998\,244\,353$ 取模后的结果。

样例

输入格式 1

5
1 5
2 5
3 5
3 3
123 456

输出格式 1

16
2
64
16
400944928