Background

Special for beginners, ^_^

Description

现在有一个已经配平的最简化学方程式，从左到右的系数分别为q1, q2, .. qi。小明修改了这个化学方程式的系数，每个系数xi的修改范围为1<=xi<=ui。问有多少种方案使得修改后的化学方程式仍然是一个配平的化学方程式。

Format

Input

第一行一个整数T（不超过10000），表示有多少组数据。 对于后面的每组数据，第一行先给出一个数字n（不超过1e5），表示从左到右有多少种反应物或者生成物。 第二行给出已经配平的最简化学方程式，从左到右的系数分别为q1, q2, .. qn。 第三行给出了每个系数的修改的上界u1, u2, .. un。0 < qi,ui, <= 1e18。

Output

输出一个整数，表示方案数。

Samples

2
2
3 2
3 4
4
1 6 2 3
3 2022 5 6

1
2

Limitation

1s, 1024KiB for each test case.

hint

对于样例1中的第一个例子，可以看成是2O3 = 3O2。