Given an array of $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$). Find the maximum value of $i + j$ such that $a_i$ and $a_j$ are coprime,$^{\dagger}$ or $-1$ if no such $i$, $j$ exist.

For example consider the array $[1, 3, 5, 2, 4, 7, 7]$. The maximum value of $i + j$ that can be obtained is $5 + 7$, since $a_5 = 4$ and $a_7 = 7$ are coprime.

$^{\dagger}$ Two integers $p$ and $q$ are coprime if the only positive integer that is a divisor of both of them is $1$ (that is, their greatest common divisor is $1$).


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10$) — the number of test cases. The description of the test cases follows.

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

The following line contains $n$ space-separated positive integers $a_1$, $a_2$,..., $a_n$ ($1 \leq a_i \leq 1000$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output a single integer  — the maximum value of $i + j$ such that $i$ and $j$ satisfy the condition that $a_i$ and $a_j$ are coprime, or output $-1$ in case no $i$, $j$ satisfy the condition.


-----Examples-----

Input
6
3
3 2 1
7
1 3 5 2 4 7 7
5
1 2 3 4 5
3
2 2 4
6
5 4 3 15 12 16
5
1 2 2 3 6
Output
6
12
9
-1
10
7


-----Note-----

For the first test case, we can choose $i = j = 3$, with sum of indices equal to $6$, since $1$ and $1$ are coprime.

For the second test case, we can choose $i = 7$ and $j = 5$, with sum of indices equal to $7 + 5 = 12$, since $7$ and $4$ are coprime.

Difficulty: EASY
Tags: Number theory

Complete search

Greedy algorithms
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
import math
x = int(input())

def do(has):
	n = len(has)
	dc = {}
	for (i, v) in enumerate(has):
		dc[v] = i
	res = -3
	if 1 in dc:
		res = max(res, dc[1] + n - 1)
		del dc[1]
	ndc = sorted(([dc[i], i] for i in dc))[::-1]
	n = len(ndc)
	for i in range(n):
		(ai, vi) = ndc[i]
		if res >= 2 * ai:
			break
		for j in range(i + 1, n):
			(aj, vj) = ndc[j]
			if math.gcd(vi, vj) == 1:
				res = max(res, ai + aj)
				break
	return res + 2
for _ in range(x):
	a = int(input())
	lis = list(map(int, input().split()))
	print(do(lis))


import math
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	p = {}
	for (i, v) in enumerate(arr):
		p[v] = i
	ans = -1
	t = sorted(p.keys(), key=lambda x: p[x])
	for i in range(len(t)):
		for j in range(len(t) - 1, i - 1, -1):
			if math.gcd(t[i], t[j]) == 1:
				ans = max(ans, p[t[i]] + p[t[j]] + 2)
				break
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for (k, v) in enumerate(l):
		d[v] = k
	m = -1
	s = sorted(d.keys(), key=lambda x: d[x])
	for i in range(0, len(s)):
		for j in range(len(s) - 1, i - 1, -1):
			if math.gcd(s[i], s[j]) == 1:
				x = d[s[i]] + d[s[j]] + 2
				m = max(m, x)
				break
	print(m)


from math import gcd
for _ in range(int(input())):
	a = int(input())
	b = input().split()
	d = {}
	for x in range(a):
		d[int(b[x])] = x
	b = []
	for x in d.items():
		b += [x]
	b.sort(key=lambda x: x[1])
	c = -3
	for x in range(1, len(b) + 1):
		for y in range(x, len(b) + 1):
			if gcd(b[-x][0], b[-y][0]) == 1:
				if c < b[-x][1] + b[-y][1]:
					c = b[-x][1] + b[-y][1]
				break
	print(c + 2)


import math
t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	hash_map = {}
	for i in range(n):
		hash_map[arr[i]] = i
	t = sorted(hash_map.keys(), key=lambda x: hash_map[x])
	ans = -1
	for i in range(len(t)):
		for j in range(len(t) - 1, -1, -1):
			if math.gcd(t[i], t[j]) == 1:
				ans = max(ans, 2 + hash_map[t[i]] + hash_map[t[j]])
				break
	print(ans)
while t:
	solve()
	t -= 1


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mx = -1
	d = {}
	for i in range(n):
		d[l[i]] = i
	lst = []
	for i in d:
		lst.append([d[i], i])
	lst = sorted(lst)
	l = []
	for (i, j) in lst:
		l.append(j)
	for i in range(len(l) - 1, -1, -1):
		if 2 * d[l[i]] + 2 <= mx:
			break
		for j in range(i, -1, -1):
			if d[l[i]] + d[l[j]] + 2 <= mx:
				break
			if math.gcd(l[i], l[j]) == 1:
				mx = max(mx, d[l[i]] + d[l[j]] + 2)
	print(mx)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mx = -1
	d = {}
	for i in range(n):
		d[l[i]] = i
	lst = []
	for i in d:
		lst.append([d[i], i])
	lst = sorted(lst)
	l = []
	for (i, j) in lst:
		l.append(j)
	n = len(l)
	for i in range(n - 1, -1, -1):
		if 2 * d[l[i]] + 2 <= mx:
			break
		for j in range(i, -1, -1):
			if d[l[i]] + d[l[j]] + 2 <= mx:
				break
			if gcd(l[i], l[j]) == 1:
				mx = max(mx, d[l[i]] + d[l[j]] + 2)
	print(mx)


import math
cache = {}
t = int(input())
for _ in range(t):
	n = int(input())
	res = -1
	nums = list(map(int, input().split()))
	seen = set()
	unique = []
	for i in range(n - 1, -1, -1):
		if nums[i] not in seen:
			seen.add(nums[i])
			unique.append((nums[i], i + 1))
	m = len(unique)
	for i in range(m):
		(val1, in1) = unique[i]
		if in1 + n <= res:
			break
		for j in range(i, m):
			(val2, in2) = unique[j]
			if in1 + in2 <= res:
				break
			(a, b) = (min(val1, val2), max(val1, val2))
			if (a, b) not in cache:
				cache[a, b] = math.gcd(a, b)
			gcd = cache[a, b]
			if gcd == 1:
				res = in1 + in2
	print(res)


from math import gcd

def highest_coprime(n, arr):
	dict = {}
	for (i, value) in enumerate(arr):
		dict[value] = i + 1
	max = -1
	for i in dict:
		for j in dict:
			if dict[i] + dict[j] > max and gcd(i, j) == 1:
				max = dict[i] + dict[j]
	print(max)

def main():
	for i in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		highest_coprime(n, arr)
main()


from math import gcd

def solve():
	coprimes = [(0, 0)] + [(i, j) for i in range(1000) for j in range(i) if gcd(i + 1, j + 1) == 1]
	t = int(input())
	for _ in range(t):
		n = int(input())
		indexes = [None] * 1000
		for (i, value) in enumerate(map(int, input().split())):
			indexes[value - 1] = i
		best = -1
		for (i, j) in coprimes:
			index_1 = indexes[i]
			index_2 = indexes[j]
			if index_1 != None != index_2:
				best = max(best, index_1 + index_2 + 2)
		print(best)
solve()


def gcd(a: int, b: int):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
arr = []
for i in range(1004):
	arr.append([])
for i in range(1, 1001):
	for j in range(i, 1001):
		if gcd(j, i) == 1:
			arr[i].append(j)
T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	num = [int(x) for x in input().strip().split(' ')]
	dis = [0] * 1005
	for i in range(n):
		if dis[num[i]] < i + 1:
			dis[num[i]] = i + 1
	ans = -1
	for i in range(1001, 0, -1):
		if dis[i] != 0:
			for j in arr[i]:
				if dis[j] != 0:
					if ans < dis[i] + dis[j]:
						ans = dis[i] + dis[j]
	print(ans)


from collections import defaultdict

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

def solve(nums, pairs):
	ans = -1
	pos = {}
	for (idx, num) in enumerate(nums):
		pos[num] = idx + 1
	for i in pos:
		for j in pairs[i]:
			if i in pos and j in pos:
				ans = max(ans, pos[i] + pos[j])
	return ans
t = int(input())
res = []
pairs = [[] for _ in range(1001)]
for i in range(1, 1001):
	for j in range(i, 1001):
		if gcd(i, j) == 1:
			pairs[i].append(j)
for _ in range(t):
	_ = input()
	nums = list(map(int, input().split()))
	res.append(solve(nums, pairs))
for r in res:
	print(r)


from math import gcd
N = int(input())
h = []
for i in range(N):
	f = -1
	k = int(input())
	b = set()
	bb = []
	a = list(map(int, input().split()))
	for i in range(k - 1, -1, -1):
		if a[i] not in b:
			b.add(a[i])
			bb.append((a[i], i + 1))
	kk = len(bb)
	for i in range(kk):
		for j in range(i, kk):
			ss = bb[i][1] + bb[j][1]
			if ss > f:
				o = bb[i][0]
				g = bb[j][0]
				if gcd(o, g) == 1:
					f = ss
					break
	h.append(f)
for t in h:
	print(t)


import math
t = int(input())
for tt in range(t):
	input()
	(*a,) = map(int, input().split())
	s = set()
	n = len(a)
	b = []
	for i in a[::-1]:
		if not i in s:
			b += [[i, n]]
			s.add(i)
		n -= 1
	N = len(b)
	best = -1
	for (i, i1) in b:
		for (j, j1) in b:
			if i1 + j1 > best and math.gcd(i, j) == 1:
				best = i1 + j1
	print(best)


import math

def solve(nums):
	result = -1
	coprimes = {}
	indices = {n: i for (i, n) in enumerate(nums)}
	for n in sorted(indices.keys(), reverse=True):
		i = indices[n]
		for k in range(1, n + 1):
			if math.gcd(n, k) == 1:
				if k not in coprimes:
					coprimes[k] = i
				else:
					coprimes[k] = max(coprimes[k], i)
		if n in coprimes:
			result = max(result, i + coprimes[n] + 2)
	return result
t = int(input())
outputs = []
for _ in range(t):
	_ = input()
	outputs.append(solve([int(i) for i in input().split(' ')]))
for output in outputs:
	print(output)


import math
gcds = [[math.gcd(i, j) for i in range(1001)] for j in range(1001)]
t = int(input())
for i in range(t):
	n = int(input())
	vals = {i: n for (n, i) in enumerate(map(int, input().split()))}
	maxsum = -1
	for (num, (row, rowind)) in enumerate(vals.items()):
		for (col, colind) in list(vals.items())[num:]:
			if gcds[row][col] == 1:
				if rowind + colind + 2 > maxsum:
					maxsum = rowind + colind + 2
	print(maxsum)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	hash = dict()
	for i in range(n):
		hash[a[i]] = i + 1
	ans = -1
	for i in hash:
		for j in hash:
			if hash[i] + hash[j] > ans and math.gcd(i, j) == 1:
				ans = max(ans, hash[i] + hash[j])
	print(ans)


from math import gcd
for test in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	vals = {}
	res = -1
	for i in range(n):
		vals[arr[i]] = i + 1
	for x in vals:
		for y in vals:
			if res < vals[x] + vals[y] and gcd(x, y) == 1:
				res = vals[x] + vals[y]
	print(res)


from math import gcd
for _ in range(int(input())):
	_max = -1
	n = int(input())
	d = {}
	arr = list(map(int, input().split()))
	for i in range(n):
		d[arr[i]] = i + 1
	for i in d:
		for j in d:
			if _max < d[i] + d[j] and gcd(i, j) == 1:
				_max = d[i] + d[j]
	print(_max)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	index_dic = {}
	for i in range(n):
		index_dic[arr[i]] = i + 1
	ans = -1
	for i in index_dic:
		for j in index_dic:
			if index_dic[i] + index_dic[j] > ans and gcd(i, j) == 1:
				ans = index_dic[i] + index_dic[j]
	print(ans)


from math import gcd

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	h = [-1 for i in range(1001)]
	for i in range(n):
		h[arr[i]] = i
	res = -1
	for i in range(1, 1001):
		if h[i] == -1:
			continue
		for j in range(i, 1001):
			if h[j] == -1:
				continue
			if gcd(i, j) == 1:
				res = max(res, h[i] + h[j] + 2)
	print(res)
for i in range(int(input())):
	solve()


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
n = int(input())
for i in range(n):
	l = int(input())
	arr = [int(_) for _ in input().split()]
	vals = {}
	for (i, item) in enumerate(arr):
		if item in vals:
			vals[item] = max(vals[item], i + 1)
		else:
			vals[item] = i + 1
	max_sum = 0
	for (x, x_value) in vals.items():
		for (y, y_value) in vals.items():
			if x_value + y_value <= max_sum:
				continue
			if gcd(x, y) == 1:
				max_sum = max(max_sum, x_value + y_value)
	if not max_sum:
		print('-1')
	else:
		print(max_sum)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = -1
	d = {}
	for i in range(n):
		d[l[i]] = i + 1
	for i in d:
		for j in d:
			if d[i] + d[j] > p and gcd(i, j) == 1:
				p = d[i] + d[j]
	print(str(p) + '\n')


import math
for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	dic = {}
	for i in range(len(v)):
		dic[v[i]] = i + 1
	ans = 0
	for i in dic:
		for j in dic:
			if dic[i] + dic[j] > ans and math.gcd(i, j) == 1:
				ans = max(ans, dic[i] + dic[j])
	print(ans if ans != 0 else -1)


from math import gcd as g

def codeforces(ar):
	ds = {}
	ind = 1
	for i in ar:
		ds[i] = ind
		ind += 1
	s = []
	for i in ds:
		s.append(i)
	ans = -1
	n = len(s)
	for i in range(n):
		for j in range(i, n):
			(a, b) = (s[i], s[j])
			if g(a, b) == 1:
				ans = max(ds[a] + ds[b], ans)
	return ans
ts = int(input())
for test in range(ts):
	n = int(input())
	ar = [int(i) for i in input().split()]
	print(codeforces(ar))


import math
for n in range(int(input())):
	s = int(input())
	l = list(map(int, input().split()))
	h = dict()
	for i in range(s):
		h[l[i]] = i + 1
	ans = -1
	for i in h:
		for j in h:
			if h[i] + h[j] > ans and math.gcd(i, j) == 1:
				ans = h[i] + h[j]
	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()))
	ans = -1
	zi = {}
	for j in range(len(a)):
		zi[a[j]] = j + 1
	for i in zi.keys():
		for j in zi.keys():
			if zi[i] + zi[j] > ans and math.gcd(i, j) == 1:
				ans = zi[i] + zi[j]
	print(ans)


def gcd(m, n):
	return m if n == 0 else gcd(n, m % n)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	hash = dict()
	for i in range(n):
		hash[a[i]] = i + 1
	ans = -1
	for i in hash:
		for j in hash:
			if hash[i] + hash[j] > ans and gcd(i, j) == 1:
				ans = max(ans, hash[i] + hash[j])
	print(ans)


from math import gcd
for _ in range(int(input())):
	har = int(input())
	kup = {}
	arr = list(map(int, input().split()))
	for i in range(har):
		kup[arr[i]] = i + 1
	sol = -1
	for i in kup:
		for j in kup:
			if kup[i] + kup[j] > sol and gcd(i, j) == 1:
				sol = max(sol, kup[i] + kup[j])
	print(sol)


from math import gcd
num_tests = int(input())
for _ in range(num_tests):
	length_list = int(input())
	data = [int(x) for x in input().split()]
	dictionary = {}
	for i in range(length_list):
		dictionary[data[i]] = i + 1
	result = -1
	for i in dictionary.keys():
		for j in dictionary.keys():
			if dictionary[i] + dictionary[j] > result and gcd(i, j) == 1:
				result = dictionary[i] + dictionary[j]
	print(result)


import math

def main():
	n = int(input())
	d = dict()
	for (i, num) in enumerate(map(int, input().split())):
		d[num] = i + 1
	ans = -1
	for i in range(1, 1001):
		for j in range(1, 1001):
			if i not in d or j not in d:
				continue
			if d[i] + d[j] < ans:
				continue
			if math.gcd(i, j) == 1:
				ans = d[i] + d[j]
	print(ans)
t = int(input())
for _ in range(t):
	main()


import math
t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	list2 = [0 for i in range(0, 1001)]
	ans = -1
	for i in range(0, n):
		list2[list1[i]] = i + 1
	for i in range(1, 1001):
		if list2[i] != 0:
			for j in range(i, 1001):
				if list2[j] != 0:
					if math.gcd(i, j) == 1:
						if list2[i] + list2[j] > ans:
							ans = list2[i] + list2[j]
	print(ans)


import sys
input = sys.stdin.readline
from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	for i in range(n):
		d[a[i]] = i + 1
	w = list(d.keys())
	maxx = -1
	for i in range(len(w)):
		for j in range(i, len(w)):
			if gcd(w[i], w[j]) < 2 and maxx < d[w[i]] + d[w[j]]:
				maxx = d[w[i]] + d[w[j]]
	print(maxx)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sum = -1
	d = {num: i + 1 for (i, num) in enumerate(l)}
	l2 = list(d.keys())
	for i in range(len(d)):
		for j in range(i, len(d)):
			if gcd(l2[i], l2[j]) == 1:
				if d[l2[i]] + d[l2[j]] > sum:
					sum = d[l2[i]] + d[l2[j]]
	print(sum)


from math import gcd
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	for i in range(n):
		dic[arr[i]] = i + 1
	ans = -1
	for i in dic:
		for j in dic:
			if dic[i] + dic[j] > ans and gcd(i, j) == 1:
				ans = dic[i] + dic[j]
	print(ans)
	t -= 1


import math
tst = int(input())
for i in range(tst):
	n = int(input())
	arr = list(map(int, input().split()))
	dic = {}
	ans = -1
	for i in range(n):
		dic[arr[i]] = i + 1
	for i in dic:
		for j in dic:
			if dic[i] + dic[j] > ans and math.gcd(i, j) == 1:
				ans = max(ans, dic[i] + dic[j])
	print(ans)


import math
from collections import *

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	d = {}
	for i in range(len(a)):
		d[a[i]] = i
	ans = 0
	t = list(set(a))
	for i in range(len(t) - 1, -1, -1):
		for j in range(i, -1, -1):
			if math.gcd(t[i], t[j]) == 1:
				ans = max(ans, d[t[i]] + d[t[j]] + 2)
	if ans == 0:
		print(-1)
		return
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from math import gcd
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	even = {}
	odd = {}
	c = 0
	for h in arr:
		c += 1
		if h % 2 == 0:
			even[h] = c
		else:
			odd[h] = c
	maxij = -1
	for i in odd:
		for j in odd:
			if gcd(i, j) == 1 and odd.get(i) + odd.get(j) > maxij:
				maxij = odd.get(i) + odd.get(j)
	for i in odd:
		for j in even:
			if gcd(i, j) == 1 and even.get(j) + odd.get(i) > maxij:
				maxij = even.get(j) + odd.get(i)
	print(maxij)


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	net = [[-1] for i in range(1001)]
	for i in range(n):
		x = A[i]
		net[x].append(i)
	maxi = -1
	for i in range(1, 1001):
		for j in range(i, 1001):
			if gcd(i, j) == 1:
				a = net[i][-1] + 1
				b = net[j][-1] + 1
				if a != 0 and b != 0:
					maxi = max(maxi, a + b)
	print(maxi)
t = int(input())
while t != 0:
	solve()
	t -= 1


from math import gcd

def solution():
	n = int(input())
	a = list(map(int, input().split()))
	ans = -1
	d = [0 for i in range(1000)]
	for i in range(n):
		d[a[i] - 1] = i
	for i in range(1000):
		for j in range(i, 1000):
			if gcd(a[d[i]], a[d[j]]) == 1:
				ans = max(ans, d[i] + d[j] + 2)
	print(ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


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

def solve(a, n):
	d = {}
	for (i, x) in enumerate(a):
		d[x] = i + 1
	b = list(d.keys())
	res = -1
	for i in range(len(b)):
		for j in range(i, len(b)):
			if math.gcd(b[i], b[j]) == 1:
				res = max(res, d[b[i]] + d[b[j]])
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(a, n))


import math

def solve(A):
	B = [0] * 1001
	for (i, e) in enumerate(A):
		B[e] = max(i + 1, B[e])
	res = -1
	for i in range(1001):
		for j in range(i, 1001):
			if B[i] != 0 and B[j] != 0 and (math.gcd(i, j) == 1):
				res = max(res, B[i] + B[j])
	return res if res != -1 else -1

def main():
	for _ in range(int(input())):
		input()
		A = [int(e) for e in input().split()]
		print(solve(A))
main()


import math

def main():
	x = int(input())
	a = []
	for m in range(x):
		y = int(input())
		b = input().split()
		a.append(b)
	for i in a:
		findmax(i)

def findmax(array):
	hm = {}
	max = -1
	for i in range(1, 1001):
		hm[i] = -1
	for j in range(len(array)):
		hm[int(array[j])] = j + 1
	for c in range(1, 1001):
		for v in range(c, 1001):
			if hm[c] != -1 and hm[v] != -1:
				if coprime(c, v) and max < hm[c] + hm[v]:
					max = hm[c] + hm[v]
	print(max)

def coprime(a, b):
	return math.gcd(a, b) == 1
main()


import math

def coprime(array):
	hashMap = {}
	maxVal = -1
	for (index, num) in enumerate(array):
		hashMap[num] = index
	keys = list(hashMap.keys())
	for i in range(len(keys)):
		for j in range(i, len(keys)):
			if math.gcd(keys[j], keys[i]) == 1:
				maxVal = max(maxVal, hashMap[keys[i]] + hashMap[keys[j]] + 2)
	return maxVal
t = int(input())
while t > 0:
	length = int(input())
	array = list(map(int, input().split(' ')))
	print(coprime(array=array))
	t -= 1


import math

def fun(arr, n):
	d = {}
	ans = -1
	for i in range(n):
		d[arr[i]] = i
	for i in range(1, 1001):
		j = i
		if i in d:
			while j <= 1000:
				if j in d:
					if math.gcd(i, j) == 1:
						ans = max(d[i] + d[j] + 2, ans)
				j = j + 1
	return ans
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(fun(arr, n))


import math
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	d = {}
	ans = -1
	for i in range(n):
		d[a[i]] = i
	w = list(d.keys())
	for i in range(len(w) - 1, -1, -1):
		for j in range(i, -1, -1):
			if math.gcd(w[i], w[j]) == 1 and ans < d[w[i]] + d[w[j]]:
				ans = d[w[i]] + d[w[j]]
	print(ans + 2 if ans != -1 else -1)


from collections import defaultdict
import math

def takeInput():
	number_size = int(input())
	nums = list(map(int, input().split(' ')))
	dictionary = defaultdict(list)
	for (ind, ele) in enumerate(nums):
		dictionary[ele].append(ind + 1)
	return (number_size, dictionary)
testcase = int(input())
for _ in range(testcase):
	(number_size, nums) = takeInput()
	answer = 0
	for first in range(1, 1001):
		if first not in nums:
			continue
		for second in range(first, 1001):
			if second not in nums:
				continue
			if math.gcd(first, second) == 1:
				if nums[first][-1] + nums[second][-1] >= answer:
					answer = nums[first][-1] + nums[second][-1]
	if answer:
		print(answer)
	else:
		print(-1)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = {num: p + 1 for (p, num) in enumerate(arr)}
	result = -1
	for a in arr.keys():
		for b in arr.keys():
			total = arr[a] + arr[b]
			if total > result and gcd(a, b) == 1:
				result = max(result, total)
	print(result)


t = int(input())

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = -1
	pos = {}
	for i in range(n):
		pos[arr[i]] = i
	for i in pos:
		for j in pos:
			if pos[i] + pos[j] + 2 > res and gcd(i, j) == 1:
				res = max(res, pos[i] + pos[j] + 2)
	print(res)


from math import gcd
t = int(input())
pairs = [0] * 1001
for a in range(1, 1001):
	pairs[a] = list()
	for b in range(1, 1001):
		if gcd(a, b) == 1:
			pairs[a].append(b)
for i in range(t):
	g = int(input())
	h = list(map(int, input().split()))
	l = [-1] * 1001
	for j in range(g):
		l[h[j]] = j
	rty = -1
	for a in range(1, 1001):
		if l[a] == -1:
			continue
		for b in pairs[a]:
			if l[b] == -1:
				continue
			df = l[a] + l[b]
			if df > rty:
				rty = df
	if rty == -1:
		print(-1)
	else:
		print(rty + 2)


import math

class T:

	def solve(self):
		n = int(input())
		l = list(map(int, input().split()))
		z = 0
		d = dict()
		for i in range(n):
			d[l[i]] = i + 1
		a = list()
		for i in d:
			a.append([i, d[i]])
		z = -1
		a_len = len(a)
		for i in range(a_len):
			for j in range(i, a_len):
				if math.gcd(a[i][0], a[j][0]) == 1:
					z = max(z, a[i][1] + a[j][1])
		return z
for t in range(int(input())):
	obj = T()
	print(obj.solve())


import math

def m_valu(dict):
	arr = list(dict.keys())
	max_elem = 0
	k_true = False
	for i in range(len(arr)):
		for j in range(i, len(arr)):
			if math.gcd(arr[i], arr[j]) == 1:
				k_true = True
				max_elem = max(max_elem, dict[arr[i]] + dict[arr[j]] + 2)
	if k_true == True:
		return max_elem
	else:
		return -1
k = int(input())
for i in range(k):
	n = int(input())
	arr = [int(j) for j in input().split()]
	dict = {}
	for k in range(len(arr)):
		dict[arr[k]] = k
	print(m_valu(dict))


from math import gcd
for i in range(int(input())):
	n = int(input())
	b = [0] * 1001
	maxx = 0
	for (i, a) in enumerate(map(int, input().split())):
		b[a] = i + 1
	for j in range(1, 1001):
		if b[j] > 0:
			for k in range(j, 1001):
				if b[k] > 0 and gcd(j, k) == 1:
					maxx = max(maxx, b[j] + b[k])
	if maxx == 0:
		print(-1)
	else:
		print(maxx)


from math import gcd
for i in range(int(input())):
	int(input())
	D = {}
	for (i, x) in enumerate(list(map(int, input().split()))):
		D[x] = i + 1
	print(max([D[x] + D[y] for x in D for y in D if gcd(x, y) == 1], default=-1))


from math import gcd

def cal(arr, n):
	d = dict()
	for i in range(n):
		d[arr[i]] = i + 1
	max_cost = -1
	for a in d.keys():
		for b in d.keys():
			if gcd(a, b) == 1:
				cost = d.get(a) + d.get(b)
				if cost > max_cost:
					max_cost = cost
	return max_cost
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(cal(a, n))


from math import gcd
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	idx = [0] * 1001
	res = -1
	for i in range(n):
		idx[array[i]] = i + 1
	for i in range(1, 1001):
		if idx[i] != 0:
			for j in range(i, 1001):
				if idx[j] != 0 and gcd(i, j) == 1:
					res = max(res, idx[i] + idx[j])
	print(res)


import math

def algorithm(mass):
	for alg in mass:
		list_arg = list(set(alg))
		sorted(list_arg)
		res_arr = {}
		for i in range(len(list_arg)):
			for j in range(i, len(list_arg)):
				if math.gcd(list_arg[i], list_arg[j]) == 1:
					if list_arg[i] not in res_arr:
						res_arr[list_arg[i]] = [list_arg[j]]
					else:
						res_arr[list_arg[i]].append(list_arg[j])
		if len(res_arr) == 0:
			print(-1)
			continue
		alg = alg[::-1]
		sz_alg = len(alg)
		index_arr = {}
		for a in list_arg:
			index = alg.index(a)
			index = sz_alg - index
			index_arr[a] = index
		max_val = -1
		for (k, val) in res_arr.items():
			v1 = index_arr[k]
			for a in val:
				v2 = index_arr[a]
				if v1 + v2 > max_val:
					max_val = v1 + v2
		print(max_val)

def parsing():
	n = int(input())
	mass = []
	while n > 0:
		k = int(input())
		st = input().split(' ')
		res = list(map(int, st))
		mass.append(res)
		n -= 1
	return mass
ms = parsing()
algorithm(ms)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = [0] * 1001
	for i in range(n):
		arr[a[i]] = i + 1
	mx = max(a)
	res = -1
	for i in range(1000, -1, -1):
		if arr[i] == 0:
			continue
		for j in range(i, -1, -1):
			if arr[j] != 0:
				if math.gcd(i, j) == 1:
					res = max(res, arr[i] + arr[j])
	print(res)


from math import gcd
GCD = [[gcd(i, j) for j in range(1, 1001)] for i in range(1, 1001)]
for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	last = {}
	for i in range(n):
		last[a[i]] = i + 1
	unique = list(set(a))
	ans = -1
	for i in range(len(unique)):
		for j in range(i, len(unique)):
			if GCD[unique[i] - 1][unique[j] - 1] == 1 and last[unique[i]] + last[unique[j]] > ans:
				ans = last[unique[i]] + last[unique[j]]
	print(ans)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	all_elements = [0] * 1001
	for i in range(n):
		all_elements[x[i]] = i + 1
	max_sum = -1
	for i in range(1, 1001):
		if all_elements[i] == 0:
			continue
		for j in range(i, 1001):
			if all_elements[j] and math.gcd(i, j) == 1:
				max_sum = max(max_sum, all_elements[i] + all_elements[j])
	print(max_sum)


import math
import random
from collections import *
from bisect import *
from time import *
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	m = [0 for _ in range(1001)]
	maxx = 0
	for i in range(1, n + 1):
		m[a[i - 1]] = i
		maxx = max(maxx, a[i - 1])
	ans = -1
	for i in range(1, 1001):
		if m[i] != 0:
			for j in range(i, 1001):
				if m[j] != 0:
					if math.gcd(i, j) == 1:
						ans = max(ans, m[i] + m[j])
	print(ans)
	t -= 1


import math
for t in range(int(input())):
	m = 0
	n = int(input())
	l = list(map(int, input().split()))
	b = 1001 * [0]
	for (i, a) in enumerate(l):
		b[a] = i + 1
	for i in range(1, 1001):
		if b[i] != 0:
			for j in range(i, 1001):
				if b[j] != 0 and math.gcd(i, j) == 1:
					m = max(m, b[i] + b[j])
	print(m if m != 0 else -1)