每个测试点时间限制：2 秒 内存限制：256 兆字节

题目描述

给定两个长度为 $n$ 的数组 $p$ 和 $s$，其中 $p$ 是某个数组 $a$ 的前缀 GCD∗，而 $s$ 是同一个数组 $a$ 的后缀 GCD。换句话说，如果数组 $a$ 存在，那么对于每个 $1 \le i \le n$，以下等式成立： pi=gcd(a1,a2,...,ai) si =gcd(ai,ai+1,…,an) 判断是否存在一个数组 $a$，使得给定的数组 $p$ 和 $s$ 可以被得到。

∗$\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"、"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

数据规模与约定

对于第一个测试用例，一个可能的数组是：$[72, 24, 3, 6, 12, 144]$。

对于第二个测试用例，可以证明这样的数组不存在。

对于第三个测试用例，存在一个数组：$[125, 125, 125, 25, 75]$。