给出两个长度为 $$$n$$$ 的数组 $$$p$$$ 和 $$$s$$$,其中 $$$p$$$ 是某个数组 $$$a$$$ 的前缀 GCD$$$^{\text{∗}}$$$,$$$s$$$ 是同一数组 $$$a$$$ 的后缀 GCD。换句话说,如果数组 $$$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)$$$。
$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由三行组成:
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \le 10^9$$$) — 数组的元素。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$s_1, s_2, \dots, s_n$$$ ($$$1 \leq s_i \le 10^9$$$) — 数组的元素。
保证所有测试用例中所有 $$$n$$$ 的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出“是"(不带引号)如果存在可以获取给定数组 $$$p$$$ 和 $$$s$$$ 的数组 $$$a$$$,并且 "No"(不带引号)否则。
您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“是", "是", "是“,和”是”将被接受为肯定答案。
示例
输入复制
5672 24 3 3 3 33 3 3 6 12 14431 2 34 5 65125 125 125 25 2525 25 25 25 754123 421 282 251125 1981 239 2233124 521 125125 121 121
输出复制
YES NO YES NO NO
注意
对于第一个测试用例,可能的数组是:[$$$72,\ 24,\ 3,\ 6,\ 12,\ 144$$$]。
对于第二个测试用例,可以证明这样的数组不存在。
对于第三个测试用例,存在一个数组:[$$$125,\ 125,\ 125,\ 25,\ 75$$$]。