[Solution] Playing with GCD Codeforces Solution

B. Playing with GCD

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer array 𝑎$a$ of length 𝑛$n$.

Does there exist an array 𝑏$b$ consisting of 𝑛+1$n+1$ positive integers such that 𝑎𝑖=gcd(𝑏𝑖,𝑏𝑖+1)$a_i=gcd(b_i,b_{i+1})$ for all 𝑖$i$ (1≤𝑖≤𝑛$1\le i\le n$)?

Note that gcd(𝑥,𝑦)$gcd(x,y)$ denotes the greatest common divisor (GCD) of integers 𝑥$x$ and 𝑦$y$.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤105$1\le t\le {10}^5$). Description of the test cases follows.

The first line of each test case contains an integer 𝑛$n$ (1≤𝑛≤105$1\le n\le {10}^5$) — the length of the array 𝑎$a$.

The second line of each test case contains 𝑛$n$ space-separated integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ representing the array 𝑎$a$ (1≤𝑎𝑖≤104$1\le a_i\le {10}^4$).

It is guaranteed that the sum of 𝑛$n$ over all test cases does not exceed 105${10}^5$.

Output

For each test case, output "YES" if such 𝑏$b$ exists, otherwise output "NO". You can print each letter in any case (upper or lower).

Note

In the first test case, we can take 𝑏=[343,343]$b=[343,343]$.

In the second test case, one possibility for 𝑏$b$ is 𝑏=[12,8,6]$b=[12,8,6]$.

In the third test case, it can be proved that there does not exist any array 𝑏$b$ that fulfills all the conditions.