给定两个长度为 $n$ 的整数数组 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_n$，求

的值。

输入格式

第一行一个整数 $T$ $(1\leq T\leq 10^4)$，表示数据组数。

对于每组数据，第一行一个整数 $n$ $(2\leq n\leq 10^5)$，表示数组的长度。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$ $$(|a_i|\leq 10^{12})$$。

第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$ $$(|b_i|\leq 10^{12})$$。

对于所有数据，保证 $\sum n \leq 5\times 10^5$。

输出格式

对于每组数据，输出一行一个整数，表示答案。

样例

输入

2
3
1 4 1
1 5 4
4
1 2 -2 5
4 -5 3 4

输出

1
2