B. AI Finds Nothing Here

Source: Codeforces 2240B
Contest: Codeforces Round 1105 (Div. 2)
Time limit: 1 second
Memory limit: 256 megabytes

Statement

Milkcat2009 has a matrix $a$ with $n$ rows and $m$ columns consisting of integers $0$ and $1$. The rows are numbered from $1$ to $n$, and the columns are numbered from $1$ to $m$. The element in the $i$-th row and $j$-th column is denoted as $a_{i,j}$.

Milkcat2009's AI scans every single submatrix$^{\text{∗}}$ of $a$ consisting of $r$ rows and $c$ columns. The AI considers the matrix clean if the bitwise XOR sum of elements in each such submatrix is equal to $0$.

Formally, the matrix $a$ is valid if and only if for all $1 \le i \le n - r + 1$ and $1 \le j \le m - c + 1$: $$ \bigoplus_{x=i}^{i+r-1} \bigoplus_{y=j}^{j+c-1} a_{x,y} = 0 $$

where $\oplus$ denotes summation with the bitwise XOR operation.

Your task is, given various sets of integers $n, m, r, c$, to count the number of clean matrices of $n$ rows and $m$ columns with respect to scanning dimensions $r$ and $c$. Since the answer can be very large, calculate it modulo $998\,244\,353$.

$^{\text{∗}}$A submatrix of a matrix is obtained by removing some rows (from the beginning and/or end) and/or columns (from the beginning and/or end) from the original matrix.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each test case consists of a single line containing four integers $n, m, r, c$ ($1 \le r \le n \le 10^9$, $1 \le c \le m \le 10^9$), representing the dimensions of the matrix and the dimensions of the scanning area, respectively.

Output

For each test case, output a single integer representing the answer modulo $998\,244\,353$.

Note

For the first test case. The only element $a_{1,1}$ must satisfy $a_{1,1} = 0$. Since $a_{1,1}$ must be $0$, there is only $1$ valid matrix: $[0]$.

For the second test case.The condition requires the XOR sum of every $1 \times 2$ submatrix to be $0$. This implies $a_{i,j} \oplus a_{i,j+1} = 0$, so $a_{i,j} = a_{i,j+1}$ for all valid $i,j$. For each row, all elements must be equal. Thus, each row can be either $[0, 0, 0]$ or $[1, 1, 1]$. With $2$ rows, there are $2^2 =4$ valid matrices.

Examples

8
1 1 1 1
2 3 1 2
2 5 2 2
3 5 2 2
4 6 2 2
100 14 52 6
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1 1

1
4
64
128
512
543661425
121099884
1