给定两个长度为 $n$ 的非负整数数组 $b$ 和 $c$。构造一个 $n \times n$ 的矩阵 $A$，其中 $A_{ij} = b_i \oplus c_j$。求矩阵 $A$ 的行列式对 $998\,244\,353$ 取模的结果。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 1000$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 5000$)。 第二行包含数组 $b_1, b_2, \dots, b_n$ ($0 \le b_i < 2^{60}$)。 第三行包含数组 $c_1, c_2, \dots, c_n$ ($0 \le c_i < 2^{60}$)。

所有测试用例的 $n$ 之和不超过 $10\,000$。

输出格式

对于每个测试用例，输出矩阵 $A$ 的行列式对 $998\,244\,353$ 取模的结果。

样例

输入 1

3
2
2 5
4 1
1
1000000000000000001
987467354324283836
4
1 2 3 4
1 2 3 4

输出 1

21
214139910
998244129

说明

第一个测试用例： $$\begin{vmatrix} 6 & 3 \\ 1 & 4 \end{vmatrix} = 6 \cdot 4 - 1 \cdot 3 = 21$$

第二个测试用例： $$|23\,792\,195\,055\,071\,677| = 23\,792\,195\,055\,071\,677$$ $23\,792\,195\,055\,071\,677 \pmod{998\,244\,353} = 214\,139\,910$

第三个测试用例： $$\begin{vmatrix} 0 & 3 & 2 & 5 \\ 3 & 0 & 1 & 6 \\ 2 & 1 & 0 & 7 \\ 5 & 6 & 7 & 0 \end{vmatrix} = -224$$ $(-224) \pmod{998\,244\,353} = 998\,244\,129$