長さ $n$ ($n \ge 2$) の整数列 $a_{1,2,\ldots,n}$ と、長さ $m$ ($m \ge 2$) の整数列 $b_{1,2,\ldots,m}$ が与えられます。これらを用いて、$c_{i,j} = a_i \oplus b_j$ ($1 \le i \le n, 1 \le j \le m$) を満たす $n \times m$ 行列 $c$ を構築します。ここで、$\oplus$ はビットごとの排他的論理和(XOR)演算を表します。
$c$ の部分長方形領域 $\begin{bmatrix} c_{i,j} & c_{i,j+1} \\ c_{i+1,j} & c_{i+1,j+1} \end{bmatrix}$ が $\begin{bmatrix} x & x + 1 \\ x + 2 & x + 3 \end{bmatrix}$ の形になる、すなわち $c_{i,j+1} = c_{i,j} + 1$、$c_{i+1,j} = c_{i,j} + 2$、および $c_{i+1,j+1} = c_{i,j} + 3$ を満たすような組 $(i, j)$ ($1 \le i < n, 1 \le j < m$) がいくつあるかを求めてください。
入力
最初の行には、テストケースの数を表す整数 $T$ ($1 \le T \le 10^5$) が与えられます。
各テストケースについて:
最初の行には、行列 $c$ の行数と列数を表す 2 つの空白区切りの整数 $n, m$ ($2 \le n, m \le 2 \times 10^5$) が与えられます。
2 行目には、$a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{30}$) を表す $n$ 個の空白区切りの整数が与えられます。
3 行目には、$b_1, b_2, \ldots, b_m$ ($0 \le b_i < 2^{30}$) を表す $m$ 個の空白区切りの整数が与えられます。
すべてのテストケースにおける $n$ の総和は $2 \times 10^5$ を超えず、$m$ の総和も $2 \times 10^5$ を超えないことが保証されています。
出力
各テストケースについて、条件を満たす組 $(i, j)$ の個数を表す整数を 1 行に出力してください。
入出力例
入力 1
5 2 2 0 2 0 1 3 3 6 4 2 6 7 10 5 4 4 6 5 1 3 1 0 2 3 7 2 7 3 1 4 0 0 1 6 5 5 5 1 7 5 3 1 3 2 7 7 6
出力 1
1 2 1 0 6