4477: B. Playing with GCD

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 (b_i,b_i+1) for all i (1 <= i <= n)?
Note that 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 <= t <= 10⁵). Description of the test cases follows.
The first line of each test case contains an integer n (1 <= n <= 10⁵) — the length of the array a.
The second line of each test case contains n space-separated integers a₁,a₂,…,a_n representing the array a (1 <= a_i <= 10⁴).
It is guaranteed that the sum of n over all test cases does not exceed 10⁵.

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

4
1
343
2
4 2
3
4 2 4
4
1 1 1 1

YES
YES
NO
YES

In the first test case, we can take b=[343,343].
In the second test case, one possibility for b is 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.