New Year and Chemistry

题号：NC231139
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\textbf{Background}$

经过了一年的奋斗，小 W 终于拿到了 CSP-S 的一等。他同样有个朴素的期待，希望大家在新的一年里，都能 OI/ACM 和 whk 两开花。

所以他和小 F 有一个化学问题。

$\textbf{Description}$

小 F 给小 W 写了一个未配平的化学方程式。 $\text A_1\sim \text A_n$ 作为反应物和生成物参加反应。
当然你已经知道了答案数列 $q$ ，即， $\textit q_1\text A_1+\textit q_2\text A_2+...+\textit q_\textit i\text A_\textit i=\!=\!=\textit q_{\textit i+1}\text A_{\textit i+1}+\textit q_{\textit i+2}\text A_{\textit i+2}+...+\textit q_\textit n\text A_\textit n$ 是一个已配平的、最简的化学方程式。
小 W 会随机生成 $n$ 个数，即数列 $a$ ，其中 $a_i$ 的生成范围是 $[1,u_i]$ 。他编写了一个程序判断填入这些计量数后，化学方程式是否正确。若化学方程式正确，程序会返回 $\textbf{true}$ 。
即，当方程式 $\textit a_1\text A_1+\textit a_2\text A_2+...+\textit a_\textit i\text A_\textit i=\!=\!=\textit a_{\textit i+1}\text A_{\textit i+1}+\textit a_{\textit i+2}\text A_{\textit i+2}+...+\textit a_\textit n\text A_\textit n$ 左右两边同种原子数量相等时，程序会返回 $\textbf{true}$ 。

请你帮小 W 求出他得到正确答案的可能方案数，即使程序返回 $\textbf{true}$ 的可能的数列 $a$ 的个数。

输入描述:

本题有多组数据。
第一行一个整数 ，表示数据组数。
对于每组数据：
- 第一行一个整数 ，意义如题所述。
- 接下来一行  个整数，即数列 。
- 接下来一行  个整数，即数列 。
单组数据内，有 。

输出描述:

对于每组数据，输出一行，即小 W 得到正确答案的可能方案数。

示例1

输入

复制

输出

复制

1
2

说明

$数据\ 1\ 说明$

为了方便，我们不妨设这个反应是 $3\text O_2=\!=\!=2\text O_3$ ，反应条件是高温加压。

当 $\text O_2$ 和 $\text O_3$ 的化学计量数范围分别为 $[1,3],[1,4]$ 时，只有 $a=\{3,2\}$ 才能使程序返回 $\textbf{true}$ 。

$数据\ 2\ 说明$

$\text F\text e_2\text O_3+6\text{HCl}=\!=\!=2\text{FeC}\text l_3+3\text H_2\text O$ ，容易发现，正确的方程式与方程式 $2\text F\text e_2\text O_3+12\text{HCl}=\!=\!=4\text{FeC}\text l_3+6\text H_2\text O$ 都能使程序返回 $\textbf{true}$ ，且所有 $a_i$ 均在 $[1,u_i]$ 范围内。

除此之外，不存在另一个合法的方程式。

备注:

令  表示标准答案，则数据保证 。