[Solution] Playing with GCD solution codeforces

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)?

Table of Contents

[Solution] Playing with GCD solution codeforces

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𝑡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.

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).

[Solution] Playing with GCD solution codeforces

input

Copy
4
1
343
2
4 2
3
4 2 4
4
1 1 1 1
output

Copy
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.

 

For Solution

“Click Here”

Leave a Comment