問題文

$n\times m$ 行列 $A=(a_{i,j})_{1\leq i\leq n,1\leq j \leq m}$ と長さ $n$ の数列 $R = ( R_1, R _ 2, \ldots, R _ n)$ および長さ $m$ の数列 $C = (C _ 1, C _ 2, \ldots, C _ m)$ が与えられます。

はじめ、$n\times m$ 行列 $B=(b_{i,j})_{1\leq i\leq n,1\leq j \leq m}$ の要素は全て $0$ です。あなたは $B$ に対して以下の $2$ 種類の操作を任意の順番で任意の回数だけ行うことができます。特に、$1$ 回も操作しなくてもよいです。以下で $\oplus$ は bit 毎の排他的論理和を表します。

• (操作1): $1\leq i\leq n$ および $0\leq x\leq R_i$ を満たす整数 $i,x$ を選択し、全ての $1\leq j\leq m$ を満たす整数 $j$ に対して $b_{i,j}\leftarrow b_{i,j}\oplus x$ と更新する。
• (操作2): $1\leq j\leq m$ および $0\leq x\leq C_j$ を満たす整数 $j,x$ を選択し、全ての $1\leq i\leq n$ を満たす整数 $i$ に対して $b_{i,j}\leftarrow b_{i,j}\oplus x$ と更新する。

あなたの目標は、全ての $1\leq i\leq n,1\leq j\leq m$ を満たす整数 $i,j$ に対して $b_{i,j}=a_{i,j}$ が成り立つようにすることです。

そのようなことが可能であるかを判定し、可能であるならば、目標を達成するまでの操作回数の最小値を求めてください。

$1$ つのファイルにつき $T$ 個のテストケースが与えられるので、その全てに対して上記の問題を解いてください。

入力

入力は以下の形式で標準入力から与えられます。

$T$
$\mathrm{testcase} _ 1$
$\mathrm{testcase} _ 2$
$\vdots$
$\mathrm{testcase} _ T$

ここで $\mathrm{testcase} _ i\ (1\leq i\leq T)$ は $i$ 番目のテストケースの入力であり、以下の形式で与えられます。

$n\ m$
$R _ 1\ R _ 2\ \cdots\ R _ n$
$C _ 1\ C _ 2\ \cdots\ C _ m$
$a _ {1, 1}\ a _ {1, 2}\ \cdots\ a _ {1, m}$
$a _ {2, 1}\ a _ {2, 2}\ \cdots\ a _ {2, m}$
$\vdots$
$a _ {n, 1}\ a _ {n, 2}\ \cdots\ a _ {n, m}$

• 入力は全て整数で与えられる。
• $1\leq T\leq 5\times 10 ^ 4$
• $1\leq n$
• $1\leq m$
• $nm \leq 5\times 10 ^ 4$
• $0\leq R _ i \lt 2 ^ {30}$
• $0\leq C _ i \lt 2 ^ {30}$
• $0\leq a _ {i, j} \lt 2 ^ {30}$
• $T$ 個のテストケースにわたる $nm$ の総和は $5\times 10 ^ 4$ 以下

出力

$T$ 行出力してください。

$i\ (1\leq i\leq T)$ 行目には、$i$ 番目のテストケースに対して、目標を達成することができない場合は -1 を、できる場合は操作回数の最小値を出力してください。

$T$ 行目の出力のあとも改行してください。

サンプル

3
3 3
3 2 1
3 2 3
1 1 1
0 0 0
2 2 2
2 3
3 5
1 2 3
1000 1000 1000
1000 1000 1000
2 1
3 4
5
0
0

5
-1
0