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.

Difficulty: interview

Starter code:

Solutions:
import math
for _ in range(int(input())):
 n=int(input())
 ar=[int(x) for x in input().split()]
 # dp=[1]*n
 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)


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)

import math
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=math.gcd(c,a[j])
 if(c==1):
  print(k)
 else:
  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)

# cook your dish here
import math

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


import math
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=math.gcd(c,a[j])
 if(c==1):
  print(k)
 else:
  print(-1)
  
 


# cook your dish here
import math
t=int(input())
for i in range(0,t):
 n=int(input())
 a=list(map(int, input().split()))
 c=a[0]
 for j in range(1,len(a)):
  c=math.gcd(c,a[j])
 if c==1:
  print(n)
 else:
  print(-1)



# cook your dish here
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)




import math
for _ in range(int(input())):
 n=int(input())
 ar=[int(x) for x in input().split()]
 # dp=[1]*n
 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)
  
 # if max(dp)==1:
 #     print(-1)
 # else:
 #     print(max(dp))
 # print(max(dp))
    
 


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

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

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)

from math import gcd

T = int(input())
ans = []

for _ in range(T):
 N = int(input())
 A = [int(i) for i in input().split()]

 # isGcd = False
 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)


def gcd(x,y):
 if(x==0):return y
 return gcd(y%x,x)

t = int(input())

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


 


























# cook your dish here
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)
  
 
 
  


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])
 if g==1:
  print(n)
 else:
  print(-1)


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])
 if g==1:
  print(n)
 else:
  print(-1)


# cook your dish here
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)

# cook your dish here
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)

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)



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()

# cook your dish here
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(a,l[i])
 if a==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)