**Playing with GCD solution codeforces** – You are given an integer array 𝑎a of length 𝑛n.

Does there exist an array 𝑏b consisting of 𝑛+1n+1 positive integers such that 𝑎𝑖=gcd(𝑏𝑖,𝑏𝑖+1)ai=gcd(bi,bi+1) for all 𝑖i (1≤𝑖≤𝑛1≤i≤n)?

## [Solution] Playing with GCD solution codeforces

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

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1≤𝑡≤1051≤t≤105). Description of the test cases follows.

The first line of each test case contains an integer 𝑛n (1≤𝑛≤1051≤n≤105) — the length of the array 𝑎a.

The second line of each test case contains 𝑛n space-separated integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an representing the array 𝑎a (1≤𝑎𝑖≤1041≤ai≤104).

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

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

## [Solution] Playing with GCD solution codeforces

YES YES NO YES

## [Solution] Playing with GCD solution codeforces

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.