You are given an array $a$ consisting of $n$ positive integers.

You are allowed to perform this operation any number of times (possibly, zero):

choose an index $i$ ($2 \le i \le n$), and change $a_i$ to $a_i - a_{i-1}$.

Is it possible to make $a_i=0$ for all $2\le i\le n$?


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 100$)  — the number of test cases. The description of the test cases follows.

The first line contains one integer $n$ ($2 \le n \le 100$) — the length of array $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

For each test case, print "YES" (without quotes), if it is possible to change $a_i$ to $0$ for all $2 \le i \le n$, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).


-----Examples-----

Input
4
2
5 10
3
1 2 3
4
1 1 1 1
9
9 9 8 2 4 4 3 5 3
Output
YES
YES
YES
NO


-----Note-----

In the first test case, the initial array is $[5,10]$. You can perform $2$ operations to reach the goal:

Choose $i=2$, and the array becomes $[5,5]$.

Choose $i=2$, and the array becomes $[5,0]$.

In the second test case, the initial array is $[1,2,3]$. You can perform $4$ operations to reach the goal:

Choose $i=3$, and the array becomes $[1,2,1]$.

Choose $i=2$, and the array becomes $[1,1,1]$.

Choose $i=3$, and the array becomes $[1,1,0]$.

Choose $i=2$, and the array becomes $[1,0,0]$.

In the third test case, you can choose indices in the order $4$, $3$, $2$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
T = int(input())
for t in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	marker = True
	for i in range(1, n):
		if l[i] / l[0] == l[i] // l[0]:
			continue
		else:
			marker = False
			break
	if not marker:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = input().split(' ')
	b = 'YES'
	for i in a[1:]:
		if int(i) % int(a[0]) != 0:
			b = 'NO'
			break
	print(b)


for loop in range(int(input())):
	n = int(input())
	arr = input().split()
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	flag = 0
	current = arr[0]
	for i in arr:
		if i % arr[0] != 0:
			flag = 1
			break
		current = i
	if arr[1] < arr[0]:
		flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if not any((arr[i] % arr[0] for i in range(1, n))):
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ok = 1
	for i in range(1, n):
		if l[i] % l[0] != 0:
			ok = 0
			break
	if ok:
		print('YES')
	else:
		print('NO')


import collections
import math

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))
for _ in range(ii()):
	n = ii()
	a = li()
	for i in range(1, n):
		if a[i] % a[0]:
			print('NO')
			break
	else:
		print('YES')


import math
import os
import collections
import sys
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	t = A[0]
	val = 1
	for i in range(1, N):
		if A[i] % t != 0:
			val = 0
			break
	if val:
		print('YES')
	else:
		print('NO')


out = []
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in range(1, n):
		if a[i] % a[0] != 0:
			out.append('NO')
			break
	else:
		out.append('YES')
for i in out:
	print(i)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	e = 0
	for j in range(1, n):
		if lst[j] % lst[0] != 0:
			e += 1
			break
	if e == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	(*a,) = map(int, input().split())
	fl = True
	for i in range(1, n):
		if a[i] % a[0] != 0:
			fl = False
			break
	print('YES') if fl else print('NO')


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for r in range(1, n):
		if a[r] % a[0] != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	a2 = []
	for i in range(1, a):
		a2.append(lis[i] - lis[i - 1])
	a2.sort()
	f = 0
	for i in lis[1:]:
		if i % lis[0] != 0:
			f = 1
	if f:
		print('NO')
	else:
		print('YES')


def resi():
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n):
		if a[i] % a[0] != 0:
			print('NO')
			return
	print('YES')
for _ in range(int(input())):
	resi()


t = int(input())
for vvod in range(t):
	n = int(input())
	v = list(map(int, input().split()))
	ans = 'YES'
	for i in range(1, n):
		if v[i] % v[0] != 0:
			ans = 'NO'
			break
	print(ans)


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


t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	f = 1
	for i in range(1, n):
		if z[i] % z[i - 1] == 0:
			z[i] = z[i - 1]
		else:
			f = 0
			break
	if f:
		print('YES')
	else:
		print('NO')


def pan(c, k):
	for j in range(1, n):
		if c[j] % k != 0:
			return 'NO'
	return 'YES'
a = int(input())
for i in range(a):
	n = int(input())
	c = list(map(int, input().split()))
	k = c[0]
	print(pan(c, k))


t = int(input())
for gg in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	fl = False
	for i in range(1, n):
		if a[i] % a[0] != 0:
			fl = True
			break
	if fl:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	u = 0
	for j in lst:
		if j % lst[0] != 0:
			print('NO')
			u = 1
			break
	if u == 0:
		print('YES')


n = int(input())
for i in range(n):
	x = int(input())
	y = list(map(int, input().split()))
	k = []
	for i in range(x):
		if y[i] % y[0] == 0:
			k += ['YES']
		else:
			k += ['NO']
	if 'NO' in k:
		print('NO')
	else:
		print('YES')


from math import *
for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	gcdd = 0
	for i in ai:
		gcdd = gcd(gcdd, i)
	if gcdd == ai[0]:
		print('YES')
	else:
		print('NO')


t = int(input())
for j in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	for k in range(1, n):
		if a[k] % a[0] != 0:
			f = -1
			break
	if f == -1:
		print('NO')
	else:
		print('YES')


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	rem = arr[0]
	for i in range(1, n):
		if arr[i] % rem != 0:
			print('NO')
			return
		rem = rem
	print('YES')
t = int(input())
for _ in range(t):
	solve()


for s in [*open(0)][2::2]:
	(b, *a) = map(int, s.split())
	print('YNEOS'[max((x % b for x in a)) > 0::2])


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	ans = True
	for x in A[1:]:
		if x % A[0] != 0:
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')


from math import gcd
N = int(input())
for _ in range(N):
	n = int(input())
	a = list(map(int, input().split()))
	gc = a[0]
	for i in range(1, n):
		gc = gcd(gc, a[i])
	ok = False
	if gc == a[0]:
		ok = True
	print(['NO', 'YES'][ok])


import sys

def rall():
	return [x.strip() for x in sys.stdin.readlines()]

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')
NT = int(rl())
for ti in range(NT):
	n = int(rl())
	array = list(map(int, rl().split(' ')))
	good = False
	first = array[0]
	if all([x % first == 0 for x in array]):
		good = True
	pr('YES' if good else 'NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(c) for c in input().split(' ')]
	if all((b % a[0] == 0 for b in a[1:])):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = True
	for i in range(1, n):
		if s[i] % s[0] != 0:
			f = False
			break
	if f:
		print('YES')
	else:
		print('NO')


def func():
	n = int(input())
	arr = list(map(int, input().split()))
	mn = arr[0]
	for i in range(1, n):
		if arr[i] % mn != 0:
			print('NO')
			return
	print('YES')
tc = int(input())
while tc > 0:
	func()
	tc -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	count = 0
	for i in l:
		if i % l[0] == 0:
			count += 1
	if count == len(l):
		print('YES')
	else:
		print('NO')


import sys
try:
	mx = []
	while True:
		m = sys.stdin.readline().strip()
		if m == '':
			break
		m = list(m.split())
		mx.append(m)
except:
	pass
arrays = []
i = 1
while i < len(mx):
	if i % 2 == 0:
		arrays.append(list(map(int, mx[i])))
	i += 1
for arr in arrays:
	for i in range(1, len(arr)):
		if arr[i] % arr[0] != 0:
			print('NO')
			break
		if i == len(arr) - 1 and arr[i] % arr[0] == 0:
			print('YES')


for cases in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for i in range(1, n):
		if l[i] % l[0] != 0:
			k = 1
			break
	if k == 1:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	if any((s[j] % s[0] != 0 for j in range(1, n))):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	ans = 'YES'
	a = l[0]
	for i in range(1, n):
		if l[i] % a != 0:
			ans = 'NO'
	print(ans)


from math import gcd
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[1]
	for j in l[2:]:
		g = gcd(g, j)
	if g % l[0] == 0:
		print('YES')
	else:
		print('NO')


def isPossibleToZero(a, n):
	for i in range(1, n):
		if a[i] % a[0] != 0:
			return False
	return True
for i in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if isPossibleToZero(arr, n):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	f = 0
	for j in range(1, len(a)):
		if a[j] % a[0] != 0:
			print('NO')
			f = 1
			break
	if f == 0:
		print('YES')


import math
from collections import Counter
from collections import defaultdict
import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def solve(arr):
	k = arr[0]
	for i in range(1, len(arr)):
		ans = arr[i] - arr[i - 1]
		if ans % k != 0:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	n = get_ints()
	arr = get_ints()
	print(solve(arr))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	m = ls[0]
	ans = 'YES'
	if m == 0:
		print('NO')
	else:
		for i in range(1, n):
			if ls[i] % m != 0:
				ans = 'NO'
				break
		print(ans)


T = int(input())
while T:
	T -= 1
	N = int(input())
	A = input().split(' ')
	A = [int(i) for i in A]
	flag = 0
	if A[0] == 1:
		print('YES')
	else:
		for i in range(1, N):
			if A[i] % A[0] != 0:
				print('NO')
				flag = 1
				break
		if not flag:
			print('YES')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l[0]
	done = True
	for i in range(1, n):
		if l[i] % a != 0:
			done = False
			break
	if done == True:
		print('YES')
	else:
		print('NO')


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for i in range(1, n):
		g = gcd(g, a[i])
	print(['NO', 'YES'][g == a[0]])


from math import gcd

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


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	flag = True
	for i in a:
		if i % x != 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pm = True
	for i in range(1, len(l)):
		if l[i] % l[0] == 0 and pm:
			s = 'YES'
			pm = True
		else:
			s = 'NO'
			pm = False
			break
	print(s)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = False
	for i in l[1:]:
		if i % l[0] != 0:
			t = True
			break
	if t:
		print('NO')
	else:
		print('YES')


def solve():
	if arr[0] == 1:
		return 'YES'
	for i in range(1, n):
		if arr[i] % arr[0] != 0:
			return 'NO'
	return 'YES'
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	z = True
	for i in a[1:]:
		if i % a[0] != 0:
			print('NO')
			z = False
			break
	if z:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in range(1, n):
		if a[i] % a[0] != 0:
			cnt += 1
	if len(set(a)) == 1:
		print('YES')
	elif a[0] == 1:
		print('YES')
	elif cnt == 0:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	good = 0
	bad = 0
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = True
	for i in range(1, n):
		if arr[i] % arr[0] != 0:
			ans = False
	print('YES' if ans else 'NO')


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	if min(a) != a[0]:
		print('NO')
	else:
		k = 0
		for i in range(1, n):
			if a[i] % a[0] != 0:
				k = 1
				print('NO')
				break
		if k == 0:
			print('YES')
	t = t - 1


t = int(input())
sum = 0
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	f = 0
	for i in range(1, n):
		if l[i] % l[0] != 0:
			f = 1
	if f == 1:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ok = True
	for i in range(1, n):
		if a[i] % a[i - 1] != 0:
			ok = False
			break
		else:
			a[i] = a[i - 1]
	print('YES' if ok else 'NO')


for case in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	for k in range(1, n):
		if l[k] % l[0] == 0:
			count += 0
		else:
			count += 1
	if count == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = a[0]
	flag = False
	for i in range(1, n):
		if a[i] % d != 0:
			print('NO')
			flag = True
			break
	if flag == False:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	array = [int(x) for x in input().split()]
	m = array[0]
	flag = 0
	for j in array:
		if j % m != 0:
			flag = 1
			print('NO')
			break
	if flag == 0:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	x = arr[0]
	for i in arr:
		if i % x == 0:
			c += 1
	if c == n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	line = input().split(' ')
	nums = [int(i) for i in line]
	first = nums[0]
	good = 'YES'
	for i in range(1, n):
		if nums[i] % first != 0:
			good = 'NO'
	print(good)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	flag = 1
	for i in range(1, n):
		if l[i] % l[0] != 0:
			flag = 0
	if flag:
		print('YES')
	else:
		print('NO')


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


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 'YES'
	for i in range(1, len(a)):
		if a[i] % a[0] != 0:
			ans = 'NO'
	print(ans)


def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in a[1:]:
		if i % a[0]:
			return 'NO'
	return 'YES'

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	f = 1
	for i in range(1, n):
		if arr[i] % arr[0] != 0:
			f = 0
			break
	print('YES' if f else 'NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sum([a[i] % a[0] for i in range(1, n)])
	print('NO') if b else print('YES')


def solution(arr):
	val = a[0]
	for i in a[1:]:
		if i % val > 0:
			return 'NO'
	return 'YES'
N = int(input())
for _ in range(N):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	print(solution(a))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	c_gcd = arr[1]
	for i in range(2, n):
		c_gcd = math.gcd(c_gcd, arr[i])
	if c_gcd % arr[0] == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	if L[0] == 1:
		print('YES')
	else:
		found = True
		a = L[0]
		for i in range(1, n):
			if L[i] % a == 0:
				pass
			else:
				found = False
				break
		if found:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	flag = 0
	for i in range(1, n):
		if a[i] % a[0] != 0:
			flag = 1
	if flag == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = 0
	if arr[0] != 1:
		for i in range(1, n):
			if arr[i] % arr[0] != 0:
				flag = 1
				break
		if flag == 0:
			print('YES')
		elif flag == 1:
			print('NO')
	elif arr[0] == 1:
		print('YES')


t = int(input())
for case in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	flag = 1
	if lis[0] == 0:
		for i in range(n):
			if lis[i] != 0:
				flag = 0
	else:
		for i in range(n):
			if lis[i] % lis[0] != 0:
				flag = 0
				break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	for i in range(1, n):
		if lst[i] < lst[0] or lst[i] % lst[0] != 0:
			print('NO')
			break
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l[::-1]
	c = l[0]
	for i in range(1, n):
		if l[i] % c != 0:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	flag = 1
	for j in range(1, n):
		if x[j] % x[0] != 0:
			flag = 0
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	j = int(input())
	n = list(map(int, input().split()))
	s = 0
	d = n[0]
	n.remove(n[0])
	for i in n:
		if i % d == 0:
			continue
		else:
			s = 1
			break
	if s == 0:
		print('YES')
	else:
		print('NO')


for xyz in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(1, n):
		if arr[i] % arr[0] != 0:
			count += 1
			break
	if count > 0:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	n = int(input())
	arr_input = list(map(int, input().split(' ')))
	temp = 0
	for i in range(1, n):
		if arr_input[i] % arr_input[0] != 0:
			temp = 1
			break
	if temp == 0:
		print('YES')
	else:
		print('NO')
	t -= 1


def ss(a, n):
	c = 0
	x = a[0]
	for i in range(1, n):
		if a[i] % x != 0:
			c += 1
			break
	if c == 1:
		return 'NO'
	else:
		return 'YES'
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(ss(a, n))


def difference_operations():
	for _ in range(int(input())):
		a = int(input())
		b = list(map(int, input().split()))
		ans = ''
		for i in range(1, len(b)):
			if b[i] % b[0] == 0:
				ans = 'YES'
			else:
				ans = 'NO'
				break
		if ans == 'YES':
			print('YES')
		else:
			print('NO')
difference_operations()