Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Consider a sequence $A_{1}, A_{2}, \ldots, A_{N}$, where initially, $A_{i} = i$ for each valid $i$. You may perform any number of operations on this sequence (including zero). In one operation, you should choose two valid indices $i$ and $j$, compute the greatest common divisor of $A_{i}$ and $A_{j}$ (let's denote it by $g$), and change both $A_{i}$ and $A_{j}$ to $g$.

You are given a sequence $B_{1}, B_{2}, \ldots, B_{N}$. Is it possible to obtain this sequence, i.e. change $A$ to $B$, using the given operations?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.

------  Output ------
For each test case, print a single line containing the string "YES" if it is possible to obtain $A = B$ or "NO" if it is impossible.

------  Constraints ------
$1 ≤ N ≤ 10^{4}$
$1 ≤ B_{i} ≤ i$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{5}$

------  Subtasks ------
Subtask #1 (10 points): $N ≤ 4$

Subtask #2 (20 points): there is at most one valid index $p$ such that $B_{p} \neq p$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
2

3

1 2 2

4

1 2 3 2
----- Sample Output 1 ------ 
NO

YES
----- explanation 1 ------ 
Example case 1: We cannot make the third element of the sequence $(1, 2, 3)$ become $2$.

Example case 2: We can perform one operation with $(i, j) = (2, 4)$, which changes the sequence $(1, 2, 3, 4)$ to $(1, 2, 3, 2)$.

Difficulty: MEDIUM
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
import math
T = int(input())
for i in range(T):
	N = int(input())
	B = list(map(int, input().split()))

	def fun(i):
		t = False
		for j in B:
			if math.gcd(i + 1, j) == B[i]:
				t = True
				break
		return t
	c = 0
	for i in range(N):
		if B[i] == i + 1 or fun(i) == True:
			c = c + 1
		else:
			print('NO')
			break
	if c == N:
		print('YES')


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	input()
	print('YES' if all((i % j == 0 for (i, j) in enumerate(map(int, input().split()), 1))) else 'NO')


for _ in range(int(input())):
	input()
	print('YES' if all((i % j == 0 for (i, j) in enumerate(map(int, input().split()), 1))) else 'NO')


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


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


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


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


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


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ans = 'YES'
	for j in range(length):
		if (j + 1) % arr[j] != 0:
			ans = 'NO'
			break
	print(ans)


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


for _ in range(int(input())):
	input()
	for (i, s) in enumerate(input().split(), start=1):
		if i % int(s):
			print('NO')
			break
	else:
		print('YES')


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


import sys
import math
import bisect
import numpy as np
from sys import stdin, stdout
from itertools import accumulate, chain, combinations, groupby, permutations, product
from collections import deque, Counter
from bisect import bisect_left, bisect_right
from math import gcd, sqrt, sin, cos, tan, degrees, radians
from fractions import Fraction
from decimal import Decimal
import sys
MOD = 10 ** 9 + 7
INF = 10 ** 20
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))

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


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input())
for k in range(n):
	an = int(input())
	nums = [l for l in range(1, an + 1)]
	conv = list(map(int, input().split()))
	fin = 0
	for i in range(0, an):
		if nums[i] == conv[i]:
			fin = fin + 1
			continue
		else:
			for m in range(0, an):
				gc = gcd(nums[i], nums[m])
				if gc == conv[i]:
					fin = fin + 1
					break
	if fin == an:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	flag = False
	for i in range(n):
		if (i + 1) % arr[i] != 0:
			flag = True
			break
	if flag:
		print('NO')
	else:
		print('YES')


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


T = int(input())
for _ in range(T):
	N = int(input())
	B_arr = list(map(int, input().split()))
	A_arr = []
	for x in range(1, N + 1):
		A_arr.append(x)
	count = 0
	for x in range(N):
		if A_arr[x] % B_arr[x] == 0:
			count += 1
	if count == len(B_arr):
		print('YES')
	else:
		print('NO')


MOD = 1000000007
fact = [1] * (10 ** 6 + 1)

def pre_computation():
	for i in range(2, 10 ** 6 + 1):
		fact[i] = fact[i - 1] * i % MOD

def mod_inv(a):
	return pow(a, MOD - 2, MOD)

def nCr(n, r):
	return fact[n] * mod_inv(fact[r] * fact[n - r] % MOD)

def check(sm, a, b):
	while sm:
		if sm % 10 == a or sm % 10 == b:
			sm //= 10
		else:
			return False
	return True

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


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from queue import PriorityQueue
from queue import Queue
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
import random
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	n = sb()
	a = sd()
	for i in range(n):
		if (i + 1) % a[i] != 0:
			print('NO')
			return
	print('YES')
	return
for _ in range(sb()):
	hnbhai(_ + 1)


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	b = L()
	ans = 'YES'
	for i in range(n):
		if b[i] != i + 1 and (i + 1) % b[i]:
			ans = 'NO'
			break
	print(ans)


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


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


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


for i in range(int(input())):
	n = int(input())
	b = [int(j) for j in input().split()]
	for j in range(len(b)):
		if b[j] > j + 1 or (j + 1) % b[j] != 0:
			print('NO')
			break
	else:
		print('YES')


try:
	for i in range(int(input())):
		flag = 0
		n = int(input())
		lst = list(map(int, input().split()))
		lsta = [int(i) for i in range(1, n + 1)]
		for i in range(len(lst)):
			if lst[i] != lsta[i] and lsta[i] % lst[i] != 0:
				print('NO')
				flag = 1
				break
		if flag == 0:
			print('YES')
except:
	pass


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


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


from math import gcd
for _ in range(int(input())):
	l1 = []
	n = int(input())
	for i in range(1, n + 1):
		l1.append(i)
	l = list(map(int, input().split()))
	if l == l1:
		print('YES')
	else:
		for i in range(0, n):
			if l[i] != i + 1:
				a = 1
				if l[i] < i + 1:
					for j in l1[:i]:
						if gcd(j, i + 1) == l[i]:
							a = 0
							break
				elif l[i] > i + 1:
					print('NO')
					break
				if a == 1:
					print('NO')
					break
		if a == 0:
			print('YES')


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


try:
	t = int(input())
	for i in range(0, t):
		n = int(input())
		a = list(map(int, input().split(' ')))
		k = []
		flag = 0
		for i in range(1, n + 1):
			k.append(i)
		for i in range(0, len(a)):
			if a[i] != k[i]:
				if k[i] % a[i] != 0:
					flag = 1
					break
		if flag == 1:
			print('NO')
		else:
			print('YES')
except:
	pass


for i in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	for j in range(N):
		if (j + 1) % B[j] > 0:
			print('NO')
			break
	else:
		print('YES')


def hcfnaive(a, b):
	if b == 0:
		return a
	else:
		return hcfnaive(b, a % b)
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr1 = []
	for i in range(1, n + 1):
		arr1.append(i)
	for i in range(n):
		if arr[i] != arr1[i]:
			if hcfnaive(arr[i], arr1[i]) != arr[i]:
				print('NO')
				break
	else:
		print('YES')


import math
for test in range(int(input())):
	N = int(input())
	seq = list(map(int, input().split()))
	flag = True
	for i in range(N):
		if seq[i] == i + 1:
			continue
		elif math.gcd(seq[i], i + 1) != seq[i]:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


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


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for i in range(0, T):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = 1
	for i in range(n):
		if arr[i] == i + 1:
			continue
		elif gcd(arr[i], i + 1) != arr[i]:
			flag = 0
	if flag == 1:
		print('YES')
	else:
		print('NO')


import sys
import math
import itertools

def solve():
	n = int(input())
	a = [i for i in range(1, n + 1)]
	b = list(map(int, input().split()))
	check = True
	for (x, y) in zip(a, b):
		if x % y != 0:
			check = False
			break
	if check:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


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


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	B = [int(i) for i in input().split()]
	for i in range(1, N + 1):
		if B[i - 1] > i or i % B[i - 1] != 0:
			ans.append('NO')
			break
	else:
		ans.append('YES')
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	d = list(map(int, input().split()))
	a = 0
	p = 0
	for j in range(n):
		if d[j] != j + 1:
			p += 1
			if d[j] < j + 1 and (j + 1) % d[j] == 0:
				a += 1
	if a == p:
		print('YES')
	else:
		print('NO')


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


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


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


def seq(B):
	for (ind, val) in enumerate(B):
		if val > ind + 1:
			return 'NO'
		elif (ind + 1) % val != 0:
			return 'NO'
	return 'YES'
for t in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	print(seq(B))


for t in range(int(input())):
	n = int(input())
	store = list(map(int, input().split()))
	flag = 0
	for i in range(n):
		if store[i] != i + 1:
			if (i + 1) % store[i] == 0:
				z = store[i]
				second = 0
				for j in range(i + 1):
					if store[j] == z:
						second = 1
				if second == 1:
					continue
				else:
					flag = 1
					break
			else:
				flag = 1
				break
	if flag == 0:
		print('YES')
	else:
		print('NO')


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