两个整数 $$$x$$$ 和 $$$y$$$ 的 GCD(最大公约数)是 $$$x$$$ 和 $$$y$$$ 均可整除的最大整数 $$$z$$$。例如,$$$GCD(36, 48) = 12$$$、$$$GCD(5, 10) = 5$$$ 和 $$$GCD(7,11) = 1$$$。
Kristina 有一个数组 $$$a$$$ 恰好由 $$$n$$$ 正整数组成。她想要计算每对相邻数字的 GCD,以获得一个新数组 $$$b$$$,称为 GCD 序列。
因此,GCD 序列 $$$b$$$ 的元素将使用公式 $$$b_i = GCD(a_i, a_{i + 1})$$$ 计算,其中 $$$1 \le i \le n - 1$$$。
确定是否可以从数组 $$$a$$$ 中恰好删除一个数字,以便 GCD 序列 $$$b$$$ 是非递减的(即 $$$b_i \le b_{i+1}$$$ 始终为 true)。
例如,让 Khristina 有一个数组 $$$a$$$ = [$$$20, 6, 12, 3, 48, 36$$$]。如果她从中删除 $$$a_4 = 3$$$ 并计算 $$$b$$$ 的 GCD 序列,她会得到:
- $$$b_1 = GCD(20, 6) = 2$$$
- $$$b_2 = GCD(6, 12) = 6$$$
- $$$b_3 = GCD(12, 48) = 12$$$
- $$$b_4 = GCD(48, 36) = 12$$$
输入
输入数据的第一行包含一个数字 $$$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$$$。
输出
对于每个测试用例,输出一行:
- 如果您可以从数组 $$$a$$$ 中恰好删除一个数字,从而使 $$$b$$$ 的 GCD 序列不减,则为“是”;
- 否则为“否”。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案)。
示例
输入 #1
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
输出 #1
YES NO YES NO YES YES NO YES YES YES YES YES
注意
第一个测试用例在问题陈述中进行了解释。