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 \leq i \leq n$)?

Note that $\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 \leq t \leq 10^5$). Description of the test cases follows.

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

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ representing the array $a$ ($1 \leq a_i \leq 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).


-----Examples-----

Input
4
1
343
2
4 2
3
4 2 4
4
1 1 1 1
Output
YES
YES
NO
YES


-----Note-----

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.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print('YNEOS'[any((y % math.gcd(x, z) for (x, y, z) in zip(a, a[1:], a[2:])))::2])


from math import gcd

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in range(1, n - 1):
		g = gcd(a[i - 1], a[i + 1])
		if a[i] % g:
			print('NO')
			return
	print('YES')
t = int(input())
for _ in range(t):
	solve()


import math
t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print('YES')
		return
	for i in range(1, n - 1):
		if arr[i] % math.gcd(arr[i - 1], arr[i + 1]) != 0:
			print('NO')
			return
	print('YES')
while t:
	solve()
	t -= 1


def fast_sum(a, b, s):
	b -= (b - a) % s
	return int((a + b) / 2 * ((b - a) / s + 1))
from math import gcd

def main():
	res = []
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		if n == 1 or n == 2:
			res.append('YES')
			continue
		for i in range(n):
			if i > 0 and i < n - 1:
				if a[i] % gcd(a[i - 1], a[i + 1]) != 0:
					res.append('NO')
					break
		else:
			res.append('YES')
	print('\n'.join(res))
main()


import math
n = int(input())
for i in range(0, n):
	x = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print('YES')
	else:
		bl = True
		for k in range(0, len(a) - 2):
			if a[k + 1] % math.gcd(a[k], a[k + 2]) != 0:
				bl = False
				print('NO')
				break
		if bl:
			print('YES')


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def get_lcm(x, y):
	return x * y // math.gcd(x, y)

def solve(a, n):
	return 'YES' if all((a[i + 1] % math.gcd(a[i], a[i + 2]) == 0 for i in range(n - 2))) else 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


import sys
import math
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = 1
	for i in range(n - 2):
		if a[i + 1] % math.gcd(a[i], a[i + 2]) > 0:
			p = 0
			break
	if p == 1:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n - 1):
		if a[i] % math.gcd(a[i - 1], a[i + 1]) != 0:
			print('NO')
			break
	else:
		print('YES')


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	k = 0
	if n == 1 or n == 2:
		print('YES')
	else:
		for i in range(n - 2):
			g = math.gcd(a[i], a[i + 2])
			if a[i + 1] % g == 0:
				continue
			else:
				k = 1
				print('NO')
				break
		if k == 0:
			print('YES')


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 1
	if len(set(l)) == 1:
		print('YES')
		continue
	for i in range(1, n - 1):
		if l[i] % math.gcd(l[i - 1], l[i + 1]):
			c = 0
			break
	if c:
		print('YES')
	else:
		print('NO')


R = lambda : map(int, input().split())
(t,) = R()
import math as m
for _ in range(t):
	(n,) = R()
	a = list(R())
	s = [a[0]] + a
	q = 'YES'
	for i in range(n - 2):
		if a[i + 1] % m.gcd(a[i], a[i + 2]) != 0:
			q = 'NO'
			break
	print(q)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	flag = False
	k = len(a)
	for i in range(k - 2):
		b = gcd(a[i], a[i + 2])
		if a[i + 1] % b > 0:
			flag = True
			break
	if flag:
		print('NO')
	else:
		print('YES')


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def solve(a):
	for i in range(len(a) - 2):
		g = gcd(a[i], a[i + 2])
		if a[i + 1] % g != 0:
			return False
	return True
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	if solve(a):
		print('YES')
	else:
		print('NO')


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	curr_gcd = 1
	flag = 0
	for i in range(n - 2):
		curr_gcd = math.gcd(a[i], a[i + 2])
		if a[i + 1] % curr_gcd != 0:
			print('NO')
			flag = 1
			break
	if flag == 1:
		continue
	print('YES')


import math
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	prev = arr[0]
	for i in range(n - 1):
		b = arr[i] * arr[i + 1] // math.gcd(arr[i], arr[i + 1])
		if math.gcd(b, prev) != arr[i]:
			return 'NO'
		prev = b
	return 'YES'
for _ in range(int(input())):
	print(solve())


import math
from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 'YES'
	if n <= 2:
		print(ans)
		continue
	for j in range(n - 2):
		x = math.gcd(a[j], a[j + 2])
		if a[j + 1] % x == 0 or x == 1:
			continue
		else:
			ans = 'NO'
			break
	print(ans)


def hcf(a, b):
	if a == 0:
		return b
	return hcf(b % a, a)
for d in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	for a in range(n - 1, 1, -1):
		if ar[a - 1] % hcf(ar[a], ar[a - 2]) != 0:
			print('NO')
			break
	else:
		print('YES')


import math

def lcm(a, b):
	return a * b / math.gcd(a, b)
t = int(input())
for tc in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	ans = True
	for i in range(1, n - 1):
		if a[i] % math.gcd(a[i - 1], a[i + 1]) != 0:
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('YES')
	else:
		for i in range(1, n - 1):
			if a[i] != a[i - 1] and a[i] != a[i + 1]:
				y = math.gcd(a[i], a[i - 1])
				x = math.gcd(a[i], a[i + 1])
				if math.gcd(a[i - 1], a[i + 1]) == 1 or math.gcd(a[i - 1] // y, a[i + 1] // x) == 1:
					continue
				else:
					print('NO')
					break
		else:
			print('YES')


from math import gcd
tt = int(input())
for i in range(tt):
	n = int(input())
	L = list(map(int, input().split()))
	flag = True
	for i in range(1, len(L) - 1):
		if L[i] < gcd(L[i - 1], L[i + 1]) or L[i] % gcd(L[i - 1], L[i + 1]) != 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		res = True
	for i in range(1, n - 1):
		x = math.gcd(a[i - 1], a[i + 1])
		if a[i] % x != 0:
			res = False
			break
	if not res:
		print('NO')
	else:
		print('YES')


from math import gcd
number_of_tests = int(input())
solutions = []
for i in range(number_of_tests):
	length = int(input())
	a = [int(c) for c in input().split()]
	if length == 1 or length == 2:
		solutions.append('YES')
		continue
	for i in range(length - 2):
		divs = divmod(a[i + 1], gcd(a[i], a[i + 2]))
		if divs[0] < 1 or divs[1] != 0:
			solutions.append('NO')
			break
	else:
		solutions.append('YES')
for i in solutions:
	print(i)


from math import gcd

def lcm(i, j):
	return i * j // gcd(i, j)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[0]] + [lcm(a[i], a[i + 1]) for i in range(n - 1)] + [a[-1]]
	if a == [gcd(b[i], b[i + 1]) for i in range(n)]:
		print('YES')
	else:
		print('NO')


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)

def res():
	n = int(input())
	a = [1] + list(map(int, input().split())) + [1]
	b = (n + 2) * [1]
	for k in range(1, n + 2):
		b[k] = lcm(a[k], a[k - 1])
	for k in range(1, n + 1):
		if gcd(b[k], b[k + 1]) != a[k]:
			return 'NO'
	return 'YES'

def main():
	N = int(input())
	for i in range(N):
		print(res())
main()


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		good = True
		for i in range(n - 2):
			if a[i + 1] % gcd(a[i], a[i + 2]) != 0:
				good = False
				break
		if good:
			print('YES')
		else:
			print('NO')
main()


import math
t = int(input())
for test in range(t):
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	if n == 1 or n == 2:
		print('YES')
		continue
	q = True
	for i in range(1, n - 1):
		if a[i] % math.gcd(a[i - 1], a[i + 1]) != 0:
			q = False
	if q:
		print('YES')
	if not q:
		print('NO')


import math

def lcm(a, b):
	return a * b // math.gcd(a, b)

def cal(n, arr):
	if n == 1:
		return True
	b = [arr[0]]
	for i in range(n - 1):
		b.append(lcm(arr[i], arr[i + 1]))
	b.append(arr[-1])
	c = []
	for i in range(n):
		c.append(math.gcd(b[i], b[i + 1]))
	return c == arr
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if cal(n, arr):
		print('YES')
	else:
		print('NO')


import math

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def foo(n, a):
	b = [1] * (n + 1)
	for i in range(n):
		b[i] = lcm(b[i], a[i])
		b[i + 1] = a[i]
	for i in range(n):
		if a[i] != math.gcd(b[i], b[i + 1]):
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if foo(n, a):
		print('YES')
	else:
		print('NO')


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	last = a[0]
	for i in range(0, n - 1):
		temp = a[i] * a[i + 1]
		temp = temp // math.gcd(a[i], a[i + 1])
		if math.gcd(temp, last) != a[i]:
			print('NO')
			return
		last = temp
	print('YES')
	return
tt = inp_int()
for t in range(tt):
	solve()


from math import gcd

def is_good(cand, gcds):
	for i in range(len(gcds)):
		if gcd(cand[i], cand[i + 1]) != gcds[i]:
			return False
	return True

def find_candidate(gcds):
	cand = [1]
	for x in gcds:
		if cand[-1] % x != 0:
			cand[-1] *= x // gcd(cand[-1], x)
		cand.append(x)
	return cand

def solve():
	_ = int(input())
	a = [int(x) for x in input().split()]
	cand = find_candidate(a)
	return is_good(cand, a)
t = int(input())
for _ in range(t):
	if solve():
		print('YES')
	else:
		print('NO')


from math import gcd

def lcm(a, b):
	return abs(a * b) // gcd(a, b)

def func(a, n):
	if n <= 2:
		return 'YES'
	b = [0 for _ in range(n + 1)]
	b[0] = a[0]
	for i in range(n - 1):
		b[i + 1] = lcm(a[i], a[i + 1])
		if gcd(b[i + 1], b[i]) != a[i]:
			return 'NO'
	return 'YES'
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in list(input().split(' '))]
	print(func(a, n))


t = int(input())

def gcd(a, b):
	return gcd(b, a % b) if b != 0 else a
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	f = True
	for i in range(1, n - 1):
		if arr[i] % gcd(arr[i - 1], arr[i + 1]) != 0:
			f = False
			break
	print('YES' if f else 'NO')


import math
gcd = math.gcd
lcm = lambda x, y: x // gcd(x, y) * y

def solve(a):
	b = [a[0]]
	for i in range(0, len(a) - 1):
		b.append(lcm(a[i], a[i + 1]))
	b.append(a[-1])
	return b

def check(a, b):
	return all([a[i] == gcd(b[i], b[i + 1]) for i in range(len(a))])
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = solve(a)
	print('YES' if check(a, b) else 'NO')


import math

def main():
	for t in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = [a[0]]
		for i in range(n - 1):
			b.append(a[i] * a[i + 1] // math.gcd(a[i], a[i + 1]))
		b.append(a[-1])
		flag = True
		for i in range(len(b) - 1):
			if math.gcd(b[i], b[i + 1]) != a[i]:
				flag = False
				break
		print('YES' if flag else 'NO')
main()


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	b = [0 for x in range(n + 1)]
	for i in range(1, n):
		b[i] = lcm(arr[i], arr[i - 1])
	(b[0], b[n]) = (arr[0], arr[-1])
	f = 1
	for i in range(n):
		if arr[i] != gcd(b[i], b[i + 1]):
			f = 0
			break
	if f:
		print('YES')
	else:
		print('NO')


from math import *

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a = [1] + a + [1]
	b = [1] * (n + 2)
	for i in range(1, n + 2):
		b[i] = lcm(a[i], a[i - 1])
	for i in range(1, n + 1):
		if gcd(b[i], b[i + 1]) != a[i]:
			print('NO')
			return
	print('YES')
t = int(input())
while t:
	solve()
	t -= 1


from math import gcd
t = int(input())
for _ in range(t):
	na = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	for i in range(na - 1):
		b = a[i] * a[i + 1] // gcd(a[i], a[i + 1])
		if gcd(x, b) != a[i]:
			print('NO')
			break
		x = b
	else:
		print('YES')


import math

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * (n + 1)
	for i in range(n + 1):
		if i == 0:
			b[i] = a[i]
		elif i == n:
			b[i] = a[n - 1]
		else:
			b[i] = a[i] * a[i - 1] // math.gcd(a[i - 1], a[i])
	flag = True
	for i in range(n):
		if math.gcd(b[i], b[i + 1]) != a[i]:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	solve()
	t -= 1


import math

def lcm(x, y):
	return x // math.gcd(x, y) * y

def solve():
	n = int(input())
	a = [0] * (n + 2)
	b = [0] * (n + 2)
	a[1:n + 1] = list(map(int, input().split()))
	a[0] = a[n + 1] = 1
	for i in range(1, n + 2):
		b[i] = lcm(a[i - 1], a[i])
	for i in range(1, n + 1):
		if a[i] != math.gcd(b[i], b[i + 1]):
			print('NO')
			return
	print('YES')
t = int(input())
for _ in range(t):
	solve()


from math import *
for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n - 1):
		if 1 != gcd(a[i - 1] // gcd(a[i - 1], a[i]), a[i + 1] // gcd(a[i + 1], a[i])) and a[i] + a[i - 1] + a[i + 1] != 3:
			print('NO')
			break
	else:
		print('YES')


import math
for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	res = [lst[0]]
	for i in range(n - 1):
		res.append(lst[i] * lst[i + 1] // math.gcd(lst[i], lst[i + 1]))
		if math.gcd(res[-1], res[-2]) != lst[i]:
			print('NO')
			break
	else:
		print('YES')


import math

def lcm(a, b):
	return int(a * b / math.gcd(a, b))

def solve(a):
	b = [0] * len(a)
	b[0] = a[0]
	for i in range(1, len(a)):
		b[i] = lcm(a[i], a[i - 1])
	for i in range(1, len(a)):
		if math.gcd(b[i], b[i - 1]) != a[i - 1]:
			return 'NO'
	return 'YES'

def main():
	T = int(input())
	for _ in range(T):
		n = int(input())
		a = [int(e) for e in input().split(' ')]
		print(solve(a))
main()


import math
t = int(input())
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	curr = True
	for j in range(1, n - 1):
		if L[j] < math.gcd(L[j - 1], L[j + 1]) or L[j] % math.gcd(L[j - 1], L[j + 1]) != 0:
			curr = False
			break
	if curr:
		print('YES')
	else:
		print('NO')


from math import gcd
for i in range(int(input())):
	input()
	a = list(map(int, input().split()))
	b = [a[0]]
	for i in range(1, len(a)):
		b.append(a[i - 1] * a[i] // gcd(a[i - 1], a[i]))
		if gcd(b[i - 1], b[i]) != a[i - 1]:
			print('NO')
			break
	else:
		print('YES')


def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = input().split()
	arr = [int(i) for i in arr]
	ok = True
	for i in range(n - 2):
		val = gcd(arr[i], arr[i + 2])
		if arr[i + 1] % val != 0:
			ok = False
			break
	if ok:
		print('YES')
	else:
		print('NO')


def Gcd(x, y):
	while y:
		tmp = y
		y = x % y
		x = tmp
	return x

def Solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.append(a[-1])
	for i in range(n):
		b[i + 1] = b[i + 1] * a[i] // Gcd(b[i + 1], a[i])
	ok = True
	for i in range(n):
		if Gcd(b[i], b[i + 1]) > a[i]:
			ok = False
			break
	print('YES' if ok else 'NO')

def main():
	t = int(input())
	for test in range(t):
		Solve()
main()


from math import gcd
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	b = [nums[0]]
	for i in range(1, n):
		b.append(nums[i - 1] * nums[i] // gcd(nums[i - 1], nums[i]))
	b.append(nums[-1])
	res = 'YES'
	for i in range(n):
		if gcd(b[i], b[i + 1]) > nums[i]:
			res = 'NO'
			break
	print(res)


import math
t = int(input())

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		print('YES')
	elif n == 2:
		print('YES')
	else:
		fail = False
		prev = lcm(a[0], a[1])
		for i in range(1, n - 1):
			tmp = lcm(a[i], a[i + 1])
			if math.gcd(tmp, prev) != a[i]:
				fail = True
			prev = tmp
		if fail:
			print('NO')
		else:
			print('YES')


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	a = int(input())
	arr = list(map(int, input().split()))
	arr2 = [1 for i in range(a + 1)]
	for i in range(1, a):
		arr2[i] = lcm(arr[i - 1], arr[i])
	f = False
	for i in range(a):
		if gcd(arr2[i], arr2[i + 1]) > arr[i]:
			print('NO')
			f = True
			break
	if not f:
		print('YES')


def get_gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a

def get_lcm(a, b):
	gcd = get_gcd(a, b)
	lcm = a * b // gcd
	return lcm
output = ''
for caseno in range(int(input())):
	answer = 'YES'
	n = int(input())
	a = list(map(int, input().split()))
	preva = a[0]
	prevb = a[0]
	for i in a[1:]:
		currb = get_lcm(preva, i)
		if get_gcd(currb, prevb) != preva:
			answer = 'NO'
			break
		preva = i
		prevb = currb
	output += str(answer) + '\n'
print(output)


from math import gcd

def lcm(a, b):
	return int(a / gcd(a, b) * b)
n = int(input())
for _ in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	b.insert(0, 1)
	b.insert(a + 1, 1)
	c = [lcm(b[i], b[i - 1]) for i in range(1, a + 2)]
	for i in range(a):
		if gcd(c[i], c[i + 1]) != b[i + 1]:
			print('NO')
			break
	else:
		print('YES')


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n in [1, 2] or len(list(set(a))) == 1:
		print('YES')
		continue
	b = [-1]
	for i in range(n - 1):
		b.append(a[i] * a[i + 1] // gcd(a[i], a[i + 1]))
	b.append(-1)
	answer = 'YES'
	for i in range(1, n - 1):
		if gcd(b[i], b[i + 1]) != a[i]:
			answer = 'NO'
			break
	print(answer)


def gcd(y, z):
	while z:
		(y, z) = (z, y % z)
	return abs(y)

def solve():
	n = int(input())
	a = input().split()
	a = [int(x) for x in a]
	b = [a[0], a[0]]
	for i in range(1, n):
		x = b[-1]
		if x % a[i]:
			b[-1] = x * a[i] / gcd(x, a[i])
		b.append(a[i])
	for i in range(n):
		if gcd(b[i], b[i + 1]) != a[i]:
			print('NO')
			return
	print('YES')
t = int(input())
for k in range(t):
	solve()


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	lst = []
	lst.append(a[0])
	lst.append(a[0])
	for i in range(1, n):
		g = a[i]
		(x, y) = (lst[-1], lst[-2])
		if gcd(x, g) == g:
			lst.append(g)
		else:
			z = g // gcd(g, x)
			x = x * z
			if gcd(x, y) == a[i - 1]:
				lst.append(g)
				lst[-2] = x
			else:
				print('NO')
				break
	else:
		print('YES')


from math import gcd

def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'rgw3t3i29' == 83555:
		print('Tanmay')
	a = A()
	f = True
	prev = a[0]
	for i in range(n - 1):
		lcm = int(a[i] * a[i + 1] / gcd(a[i], a[i + 1]))
		gc = gcd(prev, lcm)
		prev = lcm
		if gc != a[i]:
			print('NO')
			f = False
			break
	if f:
		print('YES')


import math

def lcm(a, b):
	return a * b // math.gcd(a, b)
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	ans = True
	for i in range(n - 2):
		if math.gcd(lcm(a[i], a[i + 1]), lcm(a[i + 1], a[i + 2])) != a[i + 1]:
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')
	t -= 1


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	flag = True
	b = [0] * (n + 1)
	b[0] = a[0]
	b[n] = a[n - 1]
	for j in range(1, n):
		b[j] = a[j - 1] * a[j] // math.gcd(a[j - 1], a[j])
	for j in range(n):
		if a[j] != math.gcd(b[j], b[j + 1]):
			flag = False
			break
	print('YES') if flag else print('NO')


import math
for i in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	b = [0] * (x + 1)
	b[0] = a[0]
	b[1] = a[0]
	for i in range(1, x):
		b[i + 1] = a[i]
		g = math.gcd(b[i], a[i])
		b[i] = b[i] * a[i] // g
	check = 0
	for i in range(x):
		if math.gcd(b[i], b[i + 1]) != a[i]:
			check = 1
			break
	if check:
		print('NO')
	else:
		print('YES')


from math import gcd

def lcm(a, b):
	g = gcd(a, b)
	return int(a * b / g)
n = int(input())
result = []
for i in range(n):
	l = int(input())
	a = [1] + [int(x) for x in input().split()]
	b = [1]
	for j in range(1, l + 1):
		b.append(lcm(a[j], a[j - 1]))
	yes = True
	for j in range(l):
		if gcd(b[j], b[j + 1]) != a[j]:
			yes = False
			break
	if yes:
		result.append('YES')
	else:
		result.append('NO')
print(*result, sep='\n')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[0]]
	sum1 = 0
	for i in range(n - 1):
		b.append(a[i] * a[i + 1] // math.gcd(a[i], a[i + 1]))
	b.append(a[n - 1])
	for j in range(n):
		nod = math.gcd(b[j], b[j + 1])
		if a[j] == nod:
			sum1 += 1
	if sum1 == n:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [a[0]]
	for i in range(1, n):
		b.append(a[i - 1] * a[i] // math.gcd(a[i - 1], a[i]))
	b.append(a[n - 1])
	answer = 'YES'
	for i in range(n):
		if math.gcd(b[i], b[i + 1]) != a[i]:
			answer = 'NO'
	print(answer)


import math
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 'YES'
	b = [a[0]]
	for i in range(1, n):
		b.append(a[i - 1] * a[i] // math.gcd(a[i], a[i - 1]))
	b.append(a[n - 1])
	for j in range(n):
		if math.gcd(b[j], b[j + 1]) != a[j]:
			ans = 'NO'
	print(ans)


import math
import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	b = [a[0]]
	for i in range(n - 1):
		b.append(a[i] * a[i + 1] // math.gcd(a[i], a[i + 1]))
	b.append(a[-1])
	f = 1
	for i in range(n):
		if math.gcd(b[i], b[i + 1]) != a[i]:
			f = 0
			break
	if f:
		print('YES')
	else:
		print('NO')


from sys import setrecursionlimit, stdin
setrecursionlimit(1 << 20)
readline = stdin.readline
MOD = 998244353

def I():
	return int(readline())

def ST():
	return readline()[:-1]

def LI():
	return list(map(int, readline().split()))

def LII():
	return list(map(lambda x: int(x) - 1, readline().split()))

def LF(x, func):
	return [func() for _ in [0] * x]

def SPI():
	return map(int, readline().split())

def SPII():
	return map(lambda x: int(x) - 1, readline().split())

def FIE(x):
	return [readline()[:-1] for _ in [0] * x]

def gcd(x, y):
	while x:
		(x, y) = (y % x, x)
	return y

def lcm(a, b):
	return a // gcd(a, b) * b

def solve():
	N = I()
	A = LI()
	B = []
	for i in range(N + 1):
		if i == 0:
			b = A[i]
		elif i == N:
			b = A[i - 1]
		else:
			b = lcm(A[i - 1], A[i])
		B.append(b)
	AA = []
	for i in range(N):
		AA.append(gcd(B[i], B[i + 1]))
	print('YES' if A == AA else 'NO')
t = I()
for _ in range(t):
	solve()


def gcd(a, b):
	x = max(a, b)
	y = min(a, b)
	temp = y
	while temp > 0:
		y = temp
		temp = x % y
		x = y
	return x
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	if n == 1 or n == 2:
		print('YES')
	else:
		for i in range(n - 2):
			if nums[i + 1] % gcd(nums[i], nums[i + 2]) != 0:
				print('NO')
				break
		else:
			print('YES')


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi, isqrt
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	a = L()
	b = [1] * (n + 1)
	for i in range(n):
		b[i] = b[i] * a[i] // gcd(b[i], a[i])
		b[i + 1] = a[i]
	ans = 'YES'
	for i in range(n):
		if a[i] != gcd(b[i], b[i + 1]):
			ans = 'NO'
			break
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [arr[0]]
	for i in range(n - 1):
		a = arr[i] * arr[i + 1]
		g = math.gcd(arr[i], arr[i + 1])
		e = a // g
		ans.append(e)
	ans.append(arr[-1])
	f = False
	for i in range(n):
		g = math.gcd(ans[i], ans[i + 1])
		if arr[i] != g:
			f = True
			break
	if f:
		print('NO')
	else:
		print('YES')


t = int(input())

def nod(a, b):
	while a != 0 and b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b

def nok(a, b):
	return a * b / nod(a, b)

def task():
	n = int(input())
	a = list(map(int, input().split()))
	a.append(1)
	b = []
	for i in range(n + 1):
		b.append(nok(a[i], a[i - 1]))
	for i in range(n):
		if nod(b[i], b[i + 1]) != a[i]:
			return 'NO'
	return 'YES'
for test in range(t):
	print(task())


def gcd(m, n):
	while n:
		(m, n) = (n, m % n)
	return m
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * (n + 1)
	(b[0], b[n]) = (a[0], a[n - 1])
	for i in range(1, n):
		b[i] = a[i] / gcd(a[i - 1], a[i]) * a[i - 1]
	flag = 1
	for i in range(n):
		if a[i] != gcd(b[i], b[i + 1]):
			print('NO')
			flag = 0
			break
	if flag:
		print('YES')