Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

D. GCD-sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

GCD (Greatest Common Divisor) of two integers x and y is the maximum integer z by which both x and y are divisible. For example, GCD(36,48)=12, GCD(5,10)=5, and GCD(7,11)=1.

Kristina has an array a consisting of exactly n positive integers. She wants to count the GCD of each neighbouring pair of numbers to get a new array b, called GCD-sequence.

So, the elements of the GCD-sequence b will be calculated using the formula bi=GCD(ai,ai+1) for 1in1.

Determine whether it is possible to remove exactly one number from the array a so that the GCD sequence b is non-decreasing (i.e., bibi+1 is always true).

For example, let Khristina had an array a = [20,6,12,3,48,36]. If she removes a4=3 from it and counts the GCD-sequence of b, she gets:

  • b1=GCD(20,6)=2
  • b2=GCD(6,12)=6
  • b3=GCD(12,48)=12
  • b4=GCD(48,36)=12
The resulting GCD sequence b = [2,6,12,12] is non-decreasing because b1b2b3b4.
Input

The first line of input data contains a single number t (1t104) — he number of test cases in the test.

This is followed by the descriptions of the test cases.

The first line of each test case contains a single integer n (3n2105) — the number of elements in the array a.

The second line of each test case contains exactly n integers ai (1ai109) — the elements of array a.

It is guaranteed that the sum of n over all test case does not exceed 2105.

Output

For each test case, output a single line:

  • "YES" if you can remove exactly one number from the array a so that the GCD-sequence of b is non-decreasing;
  • "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer).

Example
Input
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
Output
YES
NO
YES
NO
YES
YES
NO
YES
YES
YES
YES
YES
Note

The first test case is explained in the problem statement.