## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 $n+1$ positive integers such that ${a}_{i}=gcd\left({b}_{i},{b}_{i+1}\right)$ for all $i$ ($1\le i\le n$)?

Note that $gcd\left(x,y\right)$ 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\le t\le {10}^{5}$). Description of the test cases follows.

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

The second line of each test case contains $n$ space-separated integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ representing the array $a$ ($1\le {a}_{i}\le {10}^{4}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed ${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 $b=\left[343,343\right]$.

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

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