Problem Description

Mr.I has two sequence $A_i$ and $B_i$ of length n,$(0\leq i\leq n-1)$.

Define an array $C$ of length $n$, where $ C_k={max}\{A_iB_j\}$, satisfying $(i\&j≥k)$.

$\&$ is the button under binary Bitwise AND operation.

Please calculate the value of $\sum_{i=0}^{n-1} C_i$, modulo $998244353$.

Input

The first line contains an integer $T$ . Then $T$ test cases follow.

Each test case contains three lines.

The first one contains an integer $n(1\leq n\leq {2}^{18})$ — length of the array $a$.

The second one contains $n$ integers $A_0,A_1,A_2,...,A_{n-1}(|A_i|\leq {10}^9)$

The third one contains $n$ integers $B_0,B_1,B_2,...,B_{n-1}(|B_i|\leq {10}^9)$

$\sum n \leq 2^{19}$

Output

For each test case, output a single integer $ans$,where $ans=\sum_{i=0}^{n-1} C_i$ modulo $998244353$.

1
4
9 1 4 1
5 4 1 1

54