E. XOR 矩阵
每个测试的时间限制：2 秒
内存限制：512 兆字节

对于两个数组 $a = [a_1, a_2, \dots, a_n]$ 和 $b = [b_1, b_2, \dots, b_m]$，我们定义大小为 $n \times m$ 的 XOR 矩阵 $X$，其中对于每一对 $(i, j)$（$1 \le i \le n$；$1 \le j \le m$）满足：
$X_{i,j} = a_i \oplus b_j$。
符号 $\oplus$ 表示按位异或运算。

给你四个整数 $n, m, A, B$。
统计满足以下条件的数组对 $(a, b)$ 的个数：

• $a$ 由 $n$ 个整数组成，每个整数在 $0$ 到 $A$ 之间（包含）；
• $b$ 由 $m$ 个整数组成，每个整数在 $0$ 到 $B$ 之间（包含）；
• 由这些数组形成的 XOR 矩阵中，不同数值的个数不超过 $2$。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据的组数。
每组测试数据包含一行四个整数 $n, m, A, B$（$2 \le n, m, A, B \le 2^{29} - 1$）。

输出
对于每组测试数据，输出一个整数——满足所有三个条件的数组对 $(a, b)$ 的数量。
由于这个数字可能非常大，请输出它对 $998244353$ 取模的结果。

示例
输入

6
2 2 2 2
2 3 4 5
5 7 4 3
1337 42 1337 42
4 2 13 37
536870902 536370902 536390912 466128231

输出

57
864
50360
439988899
112000
732195491