F. 随机数破解程序
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice 写了一个随机数生成器，但不幸的是，由于算法存在缺陷，这个生成器生成的数字会陷入一个长度为 $$$n$$$ 的循环。不妨设循环的第 $$$i$$$ 个数字为 $$$a_i$$$ ($$$1 \le i \le n$$$)。

Bob 拥有一个长度为 $$$m$$$ 的数组 $$$b$$$ ，他使用 Alice 的随机数生成器得到了长度为 $$$m$$$ 的数组 $$$c$$$ ，满足 $$$c_i = a_{((i-1)\ {\rm mod}\ n)+1}\ {\rm mod}\ b_i$$$($$$1 \le i \le m$$$) ，其中 $$$x\ {\rm mod}\ y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。

Bob 试图破解 Alice 的随机数生成器，也就是想获得数组 $$$a$$$ 。作为破解的第一步，给定数组 $$$b$$$ 和 $$$c$$$ ，你需要求出最小的可能的 $$$n$$$ 。

Input

输入包含多组数据。

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

对于每组数据：

第一行一个整数 $$$m(1 \le m \le 10^3)$$$ ，表示数组 $$$b$$$ 和数组 $$$c$$$ 的长度。

第二行 $$$m$$$ 个整数，第 $$$i$$$ 个整数为 $$$b_i$$$($$$1 \le b_i \le 10^6$$$) 。

第三行 $$$m$$$ 个整数，第 $$$i$$$ 个整数为 $$$c_i$$$($$$0 \le c_i \lt b_i$$$) 。

数据保证 $$$\sum m \le 10^3$$$ 。

Output

对于每组数据，输出一行一个整数，表示最小的可能的 $$$n$$$ 。

Example
Input
2
4
2 3 3 3
1 1 0 1
4
1 14 5 14
0 5 3 10
Output
2
3
Note

对于样例 1 ，一种可能的方案是 $$$a=[3,1]$$$ ，可以证明不存在 $$$n=1$$$ 的方案。

对于样例 2 ，一种可能的方案是 $$$a=[19,19,8,10]$$$ ，但这种方案不是最小的。可以构造 $$$a=[10,5,3]$$$ ，并证明不存在 $$$n=1$$$ 或 $$$n=2$$$ 的方案 。