E. Н-О-Д, не повезло!
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два массива $$$p$$$ и $$$s$$$ длины $$$n$$$, где $$$p$$$ является префиксным НОД$$$^{\text{∗}}$$$ некоторого массива $$$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$$$ могут быть получены.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Входные данные

Первая строка содержит целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите «Yes» (без кавычек), если существует массив $$$a$$$, для которого данные массивы $$$p$$$ и $$$s$$$ могут быть получены, и «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$$$].