Given an array A1,A2...AN, you have to print the size of the largest contiguous subarray such that 
GCD of all integers in that subarray is 1.

Formally,
For a subarray Ai,Ai+1...Aj where 1 ≤ i < j ≤ N to be valid: GCD(Ai,Ai+1...Aj) should be 1. You have to print the size of the largest valid subarray.
If no valid subarray exists, output -1.
Note:A single element is not considered as a subarray according to the definition of this problem.

-----Input-----
First line contains T, the number of testcases. Each testcase consists of N in one line followed by N integers in the next line.

-----Output-----
For each testcase, print the required answer in one line.

-----Constraints-----
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 105
- 1 ≤ Ai ≤ 105

-----Example-----
Input:
2
2
7 2
3
2 2 4

Output:
2
-1

-----Explanation-----
Example case 1.GCD(2,7)=1. So the subarray [A1,A2] is valid.
Example case 2.No subarray satisfies.
Note: Use scanf/print instead of cin/cout. Large input files.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Data structures

Mathematics


Solutions:
def gcd(a, k):
	while a:
		k %= a
		(k, a) = (a, k)
	return k
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] < a[1]:
		k = a[0]
	else:
		k = a[1]
	for l in a:
		k = gcd(k, l)
	if k == 1:
		print(n)
	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()))
	a = l[0]
	for i in range(1, n):
		a = gcd(l[i], a)
	if a == 1:
		print(n)
	else:
		print(-1)


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


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


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


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


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


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


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


gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
for _ in range(int(input())):
	(_, a) = (input(), list(map(int, input().split())))
	(g, m) = (0, -1)
	for (i, x) in enumerate(a):
		g = gcd(g, x)
		if g == 1 and i + 1 > m and (i != 0):
			m = i + 1
	print(m)


import math
t = int(input())
while t != 0:
	n = int(input())
	lst = list(map(int, input().split()))
	mem = lst[0]
	for i in range(1, len(lst)):
		mem = math.gcd(lst[i], mem)
	if mem == 1:
		print(n)
	else:
		print('-1')
	t -= 1


import math as b
t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	l = list(map(int, input().split()))
	p = len(l)
	m = l[0]
	for j in range(1, p):
		m = b.gcd(l[j], m)
	if m == 1:
		print(n)
	else:
		print(-1)


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


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


import math

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


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


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def gcd_of_list(arr):
	gcd = arr[0]
	for i in arr:
		gcd = math.gcd(gcd, i)
	return gcd

def main():
	for _ in tr():
		n = nl()
		a = ln()
		if gcd_of_list(a) == 1:
			print(n)
		else:
			print(-1)
main()


import sys
from os import path
if path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')
from math import gcd, floor, sqrt, log, ceil
import math
from collections import deque
read = lambda : int(input())
li = lambda : list(map(int, input().split()))
read2 = lambda : map(int, input().split())
M = 1000000007
(yes, no) = ('YES', 'NO')

def fact(n):
	return math.factorial(n)

def isPrime(n):
	if n % 2 == 0 and n != 2 or n < 2:
		return False
	i = 3
	while i * i <= n:
		if n % i == 0:
			return False
		i += 2
	return True

def solve():
	n = read()
	a = li()
	ans = a[0]
	for i in range(1, n):
		ans = gcd(ans, a[i])
	if ans == 1:
		print(n)
	else:
		print(-1)
for _ in range(int(input())):
	solve()


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


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


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	gcd = [l[0]]
	for i in range(1, len(l)):
		p = math.gcd(gcd[i - 1], l[i])
		gcd.append(p)
	ans = -1
	for j in range(len(gcd)):
		if gcd[j] == 1:
			ans = j + 1
	print(ans)


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


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, n):
		g = gcd(g, l[i])
	if g == 1:
		print(n)
	else:
		print(-1)


from math import gcd
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	a = A[0]
	for i in range(1, N):
		a = gcd(a, A[i])
	if a == 1:
		ans.append(N)
	else:
		ans.append(-1)
for i in ans:
	print(i)


from math import gcd
from functools import reduce

def find_gcd(list):
	x = reduce(gcd, list)
	return x
for _ in range(int(input())):
	(n, l) = (int(input()), list(map(int, input().split())))
	if find_gcd(l) != 1:
		print(-1)
	else:
		print(n)


t = int(input())

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


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


from math import gcd
for t in range(int(input())):
	n = int(input())
	a = sorted(set((int(i) for i in input().split())))
	l = len(a)
	for j in range(l - 1):
		if gcd(a[j], a[j + 1]) == 1:
			print(n)
			break
	else:
		print(-1)


def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)
t = int(input())
for z in range(t):
	n = int(input())
	li = [int(x) for x in input().split()]
	if 1 in li:
		print(n)
	else:
		res = li[0]
		for i in range(1, n):
			res = GCD(res, li[i])
		if res == 1:
			print(n)
		else:
			print('-1')


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	m = min(l)
	f = 0
	for j in range(2, m + 1):
		c = 0
		for k in l:
			if k % j == 0:
				c = c + 1
			else:
				break
		if c == len(l):
			f = 1
			break
	if f:
		print(-1)
	else:
		print(n)


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


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


from functools import reduce
import math

def solve():
	ans = -1
	gcd = reduce(lambda x, y: math.gcd(x, y), lst)
	if gcd == 1:
		ans = n
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	solve()


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


import math

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	g = l[0]
	for i in range(1, len(l)):
		g = math.gcd(g, l[i])
	if g == 1:
		print(n)
	else:
		print(-1)
t = int(input())
i = 0
while i < t:
	solve()
	i += 1


from math import gcd
from functools import reduce
for _ in range(int(input())):
	(n, a) = (int(input()), list(map(int, input().split())))
	print(n if reduce(gcd, a) == 1 else -1)


import math
for _ in range(int(input())):
	n = int(input())
	ar = [int(x) for x in input().split()]
	f = 0
	g = ar[0]
	for i in range(1, n):
		g = math.gcd(g, ar[i])
		if g == 1:
			f = 1
			print(n)
			break
	if f == 0:
		print(-1)


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


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


from math import *
for i in range(int(input())):
	num = int(input())
	list1 = list(map(int, input().split()))
	x = list1[0]
	for a in range(1, num):
		x = gcd(x, list1[a])
	if x == 1:
		print(num)
	else:
		print(-1)


import math
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	x = math.gcd(arr[0], arr[1])
	for element in arr[2:]:
		x = math.gcd(x, element)
	if x == 1:
		print(N)
	else:
		print(-1)


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


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

def arr_gcd(arr):
	res = arr[0]
	for i in range(1, len(arr)):
		res = gcd(res, arr[i])
	return res

def soln(n, arr):
	if arr_gcd(arr) != 1:
		return -1
	return n
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


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


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = [0] * n
	t[0] = l[0]
	for i in range(1, n):
		t[i] = gcd(l[i], t[i - 1])
	found = False
	for i in t:
		if i == 1:
			found = True
			print(n)
			break
	if not found:
		print(-1)


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


read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]
from math import gcd

def solve():
	n = read_int()
	a = read_int_arr()
	g = a[0]
	for i in a:
		g = gcd(g, i)
		if g == 1:
			break
	if g == 1:
		print(n)
	else:
		print(-1)
for _ in range(int(input())):
	solve()


def compute_hcf(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()))
	gcd = a[0]
	for i in range(len(a)):
		gcd = compute_hcf(gcd, a[i])
		if gcd == 1:
			break
	if gcd == 1:
		print(n)
	else:
		print(-1)


import math
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = l[0]
	z = 0
	for i in range(1, len(l)):
		ans = math.gcd(l[i], ans)
		if ans == 1:
			z = i + 1
		else:
			continue
	if z > 1:
		print(z)
	else:
		print(-1)


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


import math
for t in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	a = 0
	res = [0] * n
	res[0] = arr[0]
	for i in range(1, len(arr)):
		res[i] = math.gcd(arr[i], res[i - 1])
		if res[i] == 1:
			print(n)
			a = 1
			break
	if a != 1:
		print(-1)


from math import gcd

def largestgcd():
	n = int(input())
	ls = list(map(int, input().split()))
	gc = 0
	f = 0
	for i in range(n):
		gc = gcd(gc, ls[i])
		if gc == 1:
			f = 1
			break
	if f == 1:
		print(n)
	else:
		print(-1)

def __starting_point():
	for _ in range(int(input())):
		largestgcd()
__starting_point()


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


import functools
t = int(input())

def gcdn(s, n):

	def gcd(x, y):
		while y:
			(x, y) = (y, x % y)
		return x
	t = functools.reduce(lambda x, y: gcd(x, y), s)
	if t == 1:
		return n
	else:
		return -1
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	r = gcdn(s, n)
	print(r)


def gcd(firstNumber, secondNumber):
	firstNumber = int(firstNumber)
	secondNumber = int(secondNumber)
	if firstNumber < secondNumber:
		smaller = firstNumber
	else:
		smaller = secondNumber
	for i in range(1, smaller + 1):
		if firstNumber % i == 0 and secondNumber % i == 0:
			gcd = i
	return gcd
for _ in range(int(input())):
	count = int(input())
	array = input().split()
	currentGCD = array[0]
	flag = 0
	size = 0
	for i in array:
		currentGCD = gcd(i, currentGCD)
		if currentGCD == 1:
			flag = 1
			print(count)
			break
	if flag == 0:
		print(-1)


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	flag = False
	gcd = arr[0]
	for i in range(1, len(arr)):
		gcd = find_gcd(gcd, arr[i])
		if gcd == 1:
			flag = True
			break
	if flag:
		print(len(arr))
	else:
		print('-1')


from cmath import pi
from distutils import extension
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
for _ in range(ii()):
	n = ii()
	arr = il()
	res = arr[0]
	for l in range(1, n):
		res = gcd(res, arr[l])
		if res == 1:
			ot(n)
			break
	if res != 1:
		ot(-1)


def gcd(x, y):
	if not y:
		return x
	return gcd(y, x % y)
for t in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	s = False
	for i in range(len(arr) - 1):
		temp = gcd(arr[i], arr[i + 1])
		if temp == 1:
			print(len(arr))
			s = True
			break
		else:
			arr[i + 1] = temp
	if not s:
		print(-1)


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


try:

	def is_valid(x, y, d):
		q = str(x) + ',' + str(y)
		if q in d:
			return d[q]
		if y == 0:
			d[q] = x
			return x
		else:
			d[q] = is_valid(y, x % y, d)
			return d[q]
	T = int(input())
	for ijkl in range(0, T):
		n = int(input())
		a = list(map(int, input().split()))
		d = {}
		gcd = is_valid(a[0], a[1], d)
		for i in a[2:]:
			gcd = is_valid(gcd, i, d)
		if gcd == 1:
			print(n)
		else:
			print(-1)
except:
	pass


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