L. Good Matrix
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

For a $$$n \times m$$$ binary matrix $$$A$$$, if for all $$$1 \leq i \leq n, 1 \leq j \leq m$$$, the XOR of all elements in the $$$i$$$-th row and all elements in the $$$j$$$-th column equals $$$A_{i,j}$$$ (note that $$$A_{i,j}$$$ is counted twice), then the matrix is called a good matrix.

Formally, the definition of a good matrix is: $$$\forall i, j \quad (1 \leq i \leq n, 1 \leq j \leq m), \quad \left( \bigoplus_{k=1}^{m} A_{i,k} \right) \oplus \left( \bigoplus_{k=1}^{n} A_{k,j} \right) = A_{i,j}$$$

Given $$$n$$$ and $$$m$$$, you need to find the number of good matrices. Since the answer can be very large, output the result modulo $$$998\,244\,353$$$.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2 \times 10^5$$$), denoting the number of testcases.

For each test case,

Only one line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 10^{18}$$$), denoting the number of rows and columns of the matrix.

Output

For each test case, output a single integer in a line, denoting the number of good matrices modulo $$$998\,244\,353$$$.

Example
Input
5
1 5
2 5
3 5
3 3
123 456
Output
16
2
64
16
400944928