题目描述

给出两个数列 \(a_1, \ldots, a_n\) 和 \(b_1, \ldots, b_n\)，定义矩阵 \(C_{i, j} = (a_i\oplus b_j) \cdot ( \varphi(a_i)+ \varphi(b_j))\) （其中 \(\oplus\) 为按位异或， \(\varphi\) 为欧拉函数），求 \((\det C)\bmod 998\ 244\ 353\)。

输入格式

本题有多组测试数据。输入的第一行有一个正整数 \(T\) （\(1 \le T \le 100\)），表示数据组数。

对于每组测试数据：

第一行输入一个正整数 \(n\) （\(1 \le n \le 10^5\)），表示矩阵阶数。

第二行输入 \(n\) 个正整数 \(a_1, \ldots, a_n\) （\(1 \le a_i \le 10^7\)）。

第三行输入 \(n\) 个正整数 \(b_1, \ldots, b_n\) （\(1 \le b_i \le 10^7\)）。

保证所有测试数据的 \(n\) 之和不超过 \(5 \times 10^5\)。

输出格式

对于每组测试数据，输出一行一个自然数，表示 \(\det C\) 对 \(998\ 244\ 353\) 取余的结果。

样例输入

1
2
1 2
3 4

样例输出

63

提示

\(C = \begin{pmatrix}6&15\\3&18\end{pmatrix}\)。