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

НОД (наибольший общий делитель) двух целых чисел $$$x$$$ и $$$y$$$ — это такое максимальное целое число $$$z$$$, на которое нацело делятся и $$$x$$$, и $$$y$$$. Например, $$$НОД(36, 48) = 12$$$, $$$НОД(5, 10) = 5$$$, а $$$НОД(7,11) = 1$$$.

У Кристины есть массив $$$a$$$, состоящий ровно из $$$n$$$ целых положительных чисел. Она хочет посчитать НОД каждой соседней пары чисел, чтобы получить новый массив $$$b$$$, называемый НОД-последовательностью.

Таким образом, элементы НОД-последовательности $$$b$$$ будут вычисляться по формуле $$$b_i = НОД(a_i, a_{i + 1})$$$ для $$$1 \le i \le n - 1$$$.

Определите, можно ли удалить из массива $$$a$$$ ровно одно число, чтобы НОД-последовательность $$$b$$$ получилась неубывающей (то есть, всегда было верно $$$b_i \le b_{i+1}$$$)

Например, пусть у Кристины был массив $$$a$$$ = [$$$20, 6, 12, 3, 48, 36$$$]. Если она удалит из него $$$a_4 = 3$$$ и посчитает НОД-последовательность $$$b$$$, то получит:

  • $$$b_1 = НОД(20, 6) = 2$$$
  • $$$b_2 = НОД(6, 12) = 6$$$
  • $$$b_3 = НОД(12, 48) = 12$$$
  • $$$b_4 = НОД(48, 36) = 12$$$
Полученная НОД-последовательность $$$b$$$ = [$$$2,6,12,12$$$] является неубывающей, так как $$$b_1 \le b_2 \le b_3 \le b_4$$$.
Входные данные

Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка каждого набора содержит единственное целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$.

Вторая строка каждого набора содержит ровно $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

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

Выведите:

  • «YES», если можно удалить из массива $$$a$$$ ровно одно число так, чтобы НОД-последовательность $$$b$$$ получилась неубывающей;
  • «NO» в противном случае.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
12
6
20 6 12 3 48 36
4
12 6 3 4
3
10 12 3
5
32 16 8 4 2
5
100 50 2 10 20
4
2 4 8 1
10
7 4 6 2 4 5 1 4 2 8
7
5 9 6 8 5 9 2
6
11 14 8 12 9 3
9
5 7 3 10 6 3 12 6 3
3
4 2 4
8
1 6 11 12 6 12 3 6
Выходные данные
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
Примечание

Первый набор входных данных разобран в условии задачи.