当前没有测试数据。

题目描述

给定两个长度为 $n$ 的数组 $p$ 和 $s$，其中 $p$ 是某个数组 $a$ 的前缀最大公约数，$s$ 是同一个数组 $a$ 的后缀最大公约数。

形式化地说，若数组 $a$ 存在，则对于每个 $1 \le i \le n$，以下两个等式必须同时成立：

• $p_i = \gcd(a_1, a_2, \dots, a_i)$
• $s_i = \gcd(a_i, a_{i+1}, \dots, a_n)$

请你判断是否存在这样的数组 $a$，使得给定的数组 $p$ 和 $s$ 可以由 $a$ 得到。

其中 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例包含三行输入：

• 第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。
• 第二行输入 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le 10^9$），表示前缀最大公约数数组 $p$。
• 第三行输入 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$），表示后缀最大公约数数组 $s$。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行结果：

• 如果存在满足条件的数组 $a$，输出 Yes。
• 否则，输出 No。

输出时不区分大小写，例如 yEs、YES 等均视为合法输出。

输入输出样例

输入样例

5
6
72 24 3 3 3 3
3 3 3 6 12 144
3
1 2 3
4 5 6
5
125 125 125 25 25
25 25 25 25 75
4
123 421 282 251
125 1981 239 223
3
124 521 125
125 121 121

输出样例

YES
NO
YES
NO
NO

说明/提示

• 对于第一个测试用例，一个合法的数组 $a$ 是：$\{72, 24, 3, 6, 12, 144\}$。
• 对于第二个测试用例，可以证明不存在满足条件的数组 $a$。
• 对于第三个测试用例，一个合法的数组 $a$ 是：$\{125, 125, 125, 25, 75\}$。