Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

The *greatest common divisor* (GCD) of a sequence is the greatest positive integer which divides each element of this sequence.

You are given a sequence $A$ of positive integers with size $N$. You are allowed to delete up to $N-1$ elements from this sequence. (I.e., you may delete any number of elements, including zero, as long as the resulting sequence is non-empty.) 

Please find the minimum number of elements which have to be deleted so that the GCD of the resulting sequence would be equal to $1$, or determine that it is impossible.

------  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 $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum number of elements to delete, or $-1$ if it is impossible to make the GCD equal to $1$.

------  Constraints ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1,000$
$1 ≤ A_{i} ≤ 50,000$ for each valid $i$

------  Subtasks ------
Subtask #1 (20 points): $2 ≤ N ≤ 3$

Subtask #2 (80 points): original constraints

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

2

2 3

2

2 4
----- Sample Output 1 ------ 
0

-1
----- explanation 1 ------ 
Example case 1: The GCD is already equal to $1$, so the answer is $0$.

Example case 2: It is impossible to make the GCD equal to $1$, so the answer is $-1$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, n):
		g = math.gcd(g, l[i])
	if g == 1:
		print(0)
	else:
		print(-1)


def gcd(X, Y):
	while Y:
		(X, Y) = (Y, X % Y)
	return X
for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	num1 = A[0]
	num2 = A[1]
	gcd1 = gcd(num1, num2)
	for i in range(2, len(A)):
		gcd1 = gcd(gcd1, A[i])
	if gcd1 == 1:
		print('0')
	else:
		print('-1')


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[0]
	c = 0
	for i in range(1, n):
		if math.gcd(b, a[i]) == 1:
			c += 1
			b = a[i]
		else:
			c = 0
	if c > 0:
		print('0')
	else:
		print('-1')


import math
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[0]
	y = 0
	for j in range(1, n):
		if math.gcd(b, a[j]) == 1:
			y += 1
			b = a[j]
		else:
			y = 0
	if y > 0:
		print('0')
	else:
		print('-1')


h = int(input())
t = []
for iin in range(0, h):
	hnc = int(input())
	tfx = str(input())
	lrt = []
	for iix in tfx.split(' '):
		lrt.append(int(iix))
	t.append(lrt)
for jjd in t:
	jjd.sort()
	ans = 0
	if jjd[0] == 0:
		jjd.pop(0)
	if len(jjd) == 1:
		print(-1)
	else:
		jui = jjd[0]
		gcd = 1
		for hnu in range(2, jui + 1):
			indi = 0
			for klr in jjd:
				if klr % hnu != 0:
					indi = 1
					break
			if indi == 1:
				continue
			elif hnu > gcd:
				ans = -1
				break
		print(ans)


def gcd(a, b):
	if b == 0:
		return abs(a)
	else:
		return gcd(b, a % b)
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	for i in range(n):
		x = gcd(x, a[i])
		if x == 1:
			break
	if x == 1:
		print(0)
	else:
		print(-1)


import math
for x in range(0, int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	val = array[0]
	for x in array:
		val = math.gcd(val, x)
	if val == 1:
		print(0)
	else:
		print(-1)


import math
a = int(input())
for i in range(a):
	b = int(input())
	t = [int(x) for x in input().split()]
	d = t[0]
	for x in t:
		d = math.gcd(d, x)
	if d == 1:
		print(0)
	else:
		print(-1)


from math import gcd

def big_gcd(arr):
	g = 0
	for i in arr:
		g = gcd(i, g)
	return g
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if big_gcd(a) == 1:
		print(0)
	else:
		print(-1)


import math as m
for I in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1):
		s = m.gcd(a[i], a[i + 1])
	if s == 1:
		print(0)
	else:
		print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	k = math.gcd(arr[0], arr[1])
	if k == 1:
		print(0)
	else:
		print(-1)


import math
t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	g = arr[0]
	for a in arr:
		g = math.gcd(a, g)
	if g == 1:
		print(0)
	else:
		print(-1)


import math
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	x = math.gcd(l[0], l[1] % l[0])
	if x == 1:
		print(0)
	else:
		print(-1)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	num = arr[0]
	for i in range(1, n):
		num = gcd(num, arr[i])
	if num != 1:
		print(-1)
	else:
		print(0)


for _ in range(int(input())):
	n = int(input())
	import math
	a = list(map(int, input().split()))
	a.sort()
	if a[1] == 0:
		x = a[1]
	else:
		x = math.gcd(a[0], a[1] % a[0])
	if x == 1:
		print(0)
	else:
		print(-1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	array.sort()
	k = gcd(array[0], array[1])
	if k == 1:
		print(0)
	else:
		print(-1)


from math import gcd
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if gcd(a[0], a[1]) == 1:
		print(0)
	else:
		print(-1)


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	g = math.gcd(A[0], A[1])
	if g == 1:
		print(0)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if l[0] == 1:
		print(0)
	else:
		for it in l:
			count = 0
			for ti in l:
				if ti % it == 0:
					count += 1
			if count == n:
				print(-1)
				break
		else:
			cp = 0
			temp = l[0]
			for i in range(n - 1):
				for j in range(i + 1, n):
					if l[j] % temp == 0:
						l[j] = 1
						cp += 1
				if cp == 0:
					break
				if l[i] != 1:
					temp = l[i]
			print(l.count(1))


import math
t = int(input())
for i in range(t):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	d = math.gcd(b[0], b[1])
	if d == 1:
		print(0)
	else:
		print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for i in range(1, n):
		g = math.gcd(g, a[i])
	if g == 1:
		print(0)
	else:
		print(-1)


t = input()
for c in range(0, int(t)):
	n = input()
	a = input().split()
	arr = []
	for x in a:
		arr.append(int(x))
	count = 0
	arr.sort()
	odd = 0
	for y in range(1, int(n)):
		if arr[y] % arr[0] == 0:
			count = count + 1
		if arr[y] % 2 == 1:
			odd = 1
	if arr[0] == 1:
		print(0)
	elif count >= int(n) - 1 or odd == 0:
		print(-1)
	else:
		print(count)


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

def tot_gcd(arr, n):
	gcd1 = arr[0]
	for i in range(1, n):
		gcd1 = gcd(gcd1, arr[i])
		if gcd1 == 1:
			return 0
	return -1
T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	print(tot_gcd(arr, n))


import math
for _ in range(int(input())):
	n = int(input())
	inp = list(map(int, input().split()))
	d = 0
	g = inp[0]
	ans = 0
	if n == 2:
		if math.gcd(inp[0], inp[1]) == 1:
			print('0')
		else:
			print('-1')
	else:
		for i in range(1, n, 1):
			ans = math.gcd(g, inp[i])
			g = ans
		if ans == 1:
			print('0')
		else:
			print('-1')


import math
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	hcf = a[0]
	f = 1
	for i in range(1, n):
		if math.gcd(hcf, a[i]) != 1:
			hcf = math.gcd(hcf, a[i])
		else:
			f = 0
			break
	if f == 0:
		print(0)
	else:
		print(-1)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	delete_set = set()
	ans_set = set()
	arr.sort()
	count = 0
	one_present = False
	for x in range(length):
		if arr[x] == 1:
			one_present = True
			break
		if arr[x] not in delete_set:
			ans_set.add(arr[x])
			for y in range(x + 1, length):
				if math.gcd(arr[x], arr[y]) > 1:
					delete_set.add(arr[y])
					count += 1
	if one_present:
		print(0)
		continue
	if len(ans_set) < 2:
		print(-1)
	else:
		print(count)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	if length == 1:
		print(-1)
		continue
	ans = arr[0]
	for x in range(1, length):
		ans = math.gcd(ans, arr[x])
	if ans == 1:
		print(0)
	else:
		print(-1)


def hcf(a, b):
	if b > a:
		return hcf(b, a)
	elif b == 0:
		return a
	else:
		return hcf(b, a % b)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	gcd = -1
	for i in a:
		if gcd == -1:
			gcd = i
		else:
			gcd = hcf(gcd, i)
	if gcd == 1:
		print(0)
	else:
		print(-1)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	flag = True
	for i in range(1, n):
		if math.gcd(arr[i], arr[i - 1]) == 1:
			flag = False
			break
	if flag:
		print(-1)
	else:
		print(0)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = gcd(l[0], l[1])
	for i in range(2, n):
		if s == 1:
			break
		else:
			s = gcd(s, l[i])
	if s == 1:
		print(0)
	else:
		print(-1)


def gcdfunc(a, b):
	if b > a:
		return gcdfunc(b, a)
	elif b == 0:
		return a
	else:
		return gcdfunc(b, a % b)
T = int(input())
for i in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	gcd = -1
	for x in arr:
		if gcd == -1:
			gcd = x
		else:
			gcd = gcdfunc(gcd, x)
	if gcd == 1:
		print(0)
	else:
		print(-1)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	L = [int(x) for x in input().split()]
	ans = L[0]
	for i in range(1, n):
		ans = gcd(ans, L[i])
	if ans == 1:
		print(0)
	else:
		print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	c = lis[0]
	for i in range(1, n):
		c = math.gcd(c, lis[i])
	if c == 1:
		print(0)
	else:
		print(-1)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = a[0]
	for i in range(1, n):
		r = gcd(r, a[i])
	if r == 1:
		print(0)
	else:
		print(-1)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for jj in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	res = l[0]
	for i in l:
		res = gcd(min(res, i), max(res, i))
	if res == 1:
		print('0')
	else:
		print('-1')


import math

def gd(li):
	z = math.gcd(li[0], li[1])
	for i in range(2, len(li)):
		z = math.gcd(z, li[i])
	return z
for M in range(int(input())):
	n = int(input())
	li = list(map(int, input().split(' ')))
	cnt = 0
	f = 0
	li.sort()
	for i in range(n):
		if len(li) == 1:
			f = 1
			break
		m = gd(li)
		if m != 1 and len(li) >= 2:
			li.remove(li[0])
			cnt += 1
		else:
			break
	if f == 1:
		print('-1')
	else:
		print(cnt)


import math
T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	if 1 in L:
		print(0)
	else:
		ans = math.gcd(L[0], L[1])
		for i in range(2, n):
			ans = math.gcd(ans, L[i])
		if ans == 1:
			print(0)
		else:
			print(-1)


from math import gcd

def check(l):
	g = l[0]
	for i in l[1:]:
		g = gcd(g, i)
		if g == 1:
			return g
	return g
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if check(l) == 1:
		print(0)
	else:
		print(-1)


def gcdfun(a, b):
	if b > a:
		return gcdfun(b, a)
	elif b == 0:
		return a
	else:
		return gcdfun(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	gcd = -1
	for item in arr:
		if gcd == -1:
			gcd = item
		else:
			gcd = gcdfun(gcd, item)
	if gcd == 1:
		print(0)
	else:
		print(-1)


def get_gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
test_case = int(input())
for _ in range(test_case):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n - 1):
		var = get_gcd(arr[i], arr[i + 1])
	if var == 1:
		print(0)
	else:
		print(-1)


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for item in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	l = list1
	num1 = l[0]
	num2 = l[1]
	gcd = find_gcd(num1, num2)
	if n > 2:
		for i in range(2, len(l)):
			gcd = find_gcd(gcd, l[i])
	else:
		pass
	if gcd == 1:
		print(0)
	else:
		print(-1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = l[0]
	for i in range(1, len(l)):
		ans = gcd(ans, l[i])
	if ans == 1:
		print('0')
	else:
		print('-1')


from math import gcd
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	gc = li[0]
	for i in range(1, n):
		gc = gcd(gc, li[i])
	if gc == 1:
		print(0)
	else:
		print(-1)


from math import *

def fungcd(a, b):
	return gcd(a, b)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	flag = 1
	for i in l[1:]:
		if fungcd(l[0], i) == 1:
			print(0)
			flag = 0
			break
	if flag:
		print(-1)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = d = 0
	while c != 1 and len(a) != 1:
		b = a[0]
		for i in a[1:]:
			if gcd(b, i) == 1:
				print(d)
				c = 1
				break
		else:
			d += 1
			a = a[1:]
	if c == 0:
		print(-1)


import math
for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	gcd = math.gcd(l[0], l[1])
	for j in range(2, n):
		gcd = math.gcd(l[j], gcd)
		if gcd == 1:
			break
	print(0 if gcd == 1 else -1)


def gcd(x, y):
	if x > y:
		(x, y) = (y, x)
	while x != 0:
		(x, y) = (y % x, x)
	return y
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = gcd(l[0], l[1])
	for j in range(2, n):
		c = gcd(l[j], c)
		if c == 1:
			break
	print(0 if c == 1 else -1)


def gcd(x, y):
	if x > y:
		(x, y) = (y, x)
	while x != 0:
		(x, y) = (y % x, x)
	return y
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	xd = gcd(a[0], a[1])
	for i in range(2, n):
		xd = gcd(a[i], xd)
		if xd == 1:
			break
	if xd == 1:
		print(0)
	else:
		print(-1)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	ans = gcd(a[0], a[1])
	for j in range(2, len(a)):
		ans = gcd(ans, a[j])
	if ans == 1:
		print(0)
	else:
		print(-1)


from math import gcd
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	g = gcd(l[0], l[1])
	for i in l:
		if i % g != 0:
			g = gcd(z, i)
	if g == 1:
		print(0)
	else:
		print(-1)