Description

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

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

& is the button under binary Bitwise AND operation.

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

Format

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≤n≤2^{18})$ — length of the array a.

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

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

∑n≤219

Output

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

Samples

1
4
9 1 4 1
5 4 1 1

54