Read problems statements in English, Mandarin Chinese and Russian as well. 

Given an array A_{1},A_{2}...A_{N}, you have to print the size of the largest contiguous subarray such that 
LCM of all integers in that subarray is equal to the product of all integers in that subarray.

Formally,
For a subarray A_{i},A_{i+1}...A_{j} where 1 ≤ i < j ≤ N to be valid: LCM(A_{i},A_{i+1}...A_{j}) should be equal to A_{i}*A_{i+1}*...*A_{j}. You have to print the size of the largest valid subarray.
If no subarray satisfies output -1.
Note:A single element is not considered a subarray according to definition in this problem.

------ Input ------ 

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

------ Output ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 50$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$

------ Example ------ 

Input:
3
2
7 2
4
2 2 3 4
3
2 2 4

Output:
2
2
-1

------ Explanation ------ 

Example case 1.LCM(2,7)=2*7. Therefore, subarray A_{1} to A_{2} satisfies.

Example case 2.The subarrays A_{2} to A_{3} and A_{3} to A_{4} are the maximum size possible.

Example case 3.No subarray will satisfy.

Warning: Use fast input/output. Large input files. Solutions may not pass in slower languages.

Update: Time limit for python=10s

Difficulty: HARD
Tags: Amortized analysis

Greedy algorithms

Number theory

Dynamic programming

Mathematics
Skill types: Dynamic programming

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
seive = [1] * (10 ** 6 + 1)
prev = [1] * (10 ** 6 + 1)
for i in range(2, len(seive)):
	if seive[i] > 1:
		continue
	t = 1
	for j in range(i, len(seive), i):
		seive[j] = i
		prev[j] = t
		t += 1
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(c) for c in input().split()]
	v = [0] * (10 ** 6 + 1)
	ans = -1
	l = 0
	for r in range(len(arr)):
		j = arr[r]
		z = -1
		while j > 1:
			d = seive[j]
			if d != z:
				l = max(l, v[d])
				v[d] = r + 1
			j = prev[j]
			z = d
		if l < r:
			ans = max(ans, r - l + 1)
	print(ans)


import sys
input = sys.stdin.readline
import math
n = 10 ** 6
dp = [0] * (n + 1)
for i in range(2, 1001):
	if dp[i] == 0:
		dp[i] = i
		j = i * i
		while j <= n:
			dp[j] = i
			j = j + i
for i in range(n + 1):
	if dp[i] == 0:
		dp[i] = i
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	prev = 0
	d = {}
	ans = -1
	for i in range(n):
		ele = arr[i]
		while ele != 1:
			x = dp[ele]
			if x in d:
				prev = max(prev, d[x] + 1)
			d[x] = i
			while ele % x == 0:
				ele = ele // x
		if i - prev != 0:
			ans = max(ans, i - prev + 1)
	print(ans)


from sys import stdin
input = stdin.readline
size = 10 ** 6 + 1
primef = [[] for i in range(size)]
prime = []
for i in range(2, size):
	if len(primef[i]) == 0:
		for j in range(i, size, i):
			primef[j].append(i)
		prime.append(i)

def nextpossible(j, length, x):
	while their[ind[x]]:
		for i in primef[a[j]]:
			their[ind[i]] -= 1
		j += 1
		length -= 1
	return [j, length]

def answer():
	for i in range(len(prime)):
		ind[prime[i]] = i
	(j, ans, length) = (0, -1, 0)
	for i in range(n):
		for x in primef[a[i]]:
			if their[ind[x]]:
				(j, length) = nextpossible(j, length, x)
			their[ind[x]] += 1
		length += 1
		if length > 1:
			ans = max(ans, length)
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = dict()
	their = [0] * len(prime)
	print(answer())


sieve = [1] * (10 ** 6 + 1)
prev = sieve.copy()
for i in range(2, len(sieve)):
	if sieve[i] > 1:
		continue
	t = 1
	for j in range(i, len(sieve), i):
		sieve[j] = i
		prev[j] = t
		t += 1
for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = -1
	v = [0] * (10 ** 6 + 1)
	l = 0
	for r in range(n):
		j = a[r]
		z = -1
		while j > 1:
			d = sieve[j]
			if d != z:
				l = max(l, v[d])
				v[d] = r + 1
			j = prev[j]
			z = d
		if l < r:
			ans = max(ans, r - l + 1)
	print(ans)


p = 10 ** 6 + 5

def sieve():
	l = [1] * p
	i = 2
	l[0] = l[1] = 0
	spf = [i for i in range(p)]
	while i * i <= p:
		if l[i]:
			for j in range(2 * i, p, i):
				l[j] = 0
				if spf[j] == j:
					spf[j] = i
		i += 1
	return (spf, [i for i in range(p) if l[i]])
(spf, prms) = sieve()

def get(x):
	s = set()
	while x > 1:
		s.add(spf[x])
		x = x // spf[x]
	return s
for _ in range(int(input())):
	n = int(input())
	prev = {}
	for x in prms:
		prev[x] = -1
	l = [int(i) for i in input().split()]
	maxi = 0
	curr = -1
	for i in range(n):
		g = get(l[i])
		for pf in g:
			curr = max(curr, prev[pf])
		if curr == -1:
			maxi = max(maxi, i - curr)
		else:
			maxi = max(maxi, i - curr)
		for pf in g:
			prev[pf] = i
	print(maxi if maxi > 1 else -1)


import sys
maxd = pow(10, 6) + 1
factors = [[] for i in range(maxd)]
for i in range(2, maxd):
	if len(factors[i]) == 0:
		for j in range(i, maxd, i):
			factors[j].append(i)
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	last = [-1] * maxd
	start = [-1] * maxd
	ans = -1
	for i in range(n):
		val = arr[i]
		x = -1
		for fact in factors[val]:
			if last[fact] != -1:
				x = max(x, last[fact])
			last[fact] = i
		if i > 0:
			start[i] = max(start[i - 1], x)
			ans = max(ans, i - start[i])
	print(ans if ans > 1 else -1)


maxlimt = int(1000000.0 + 5)
factors = [list() for i in range(maxlimt)]

def sieve():
	(factors[0], factors[1]) = (list(), list())
	for i in range(2, maxlimt):
		if len(factors[i]) == 0:
			for j in range(i, maxlimt, i):
				factors[j].append(i)
sieve()
t = int(input())
while t:
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	indices = [-1] * maxlimt
	(left, ans) = (0, 0)
	for right in range(n):
		val = arr[right]
		for x in factors[val]:
			left = max(left, indices[x] + 1)
			indices[x] = right
		dis = right - left + 1
		ans = max(ans, dis)
	if ans < 2:
		print(-1)
	else:
		print(ans)
	t -= 1


temp = [1 for i in range(10 ** 6 + 1)]
for i in range(2, 10 ** 6 + 1):
	for j in range(i, 10 ** 6 + 1, i):
		if temp[j] == 1:
			temp[j] = i

def getFactor(num):
	last = None
	factors = []
	while num > 1:
		if temp[num] != last:
			factors.append(temp[num])
		last = temp[num]
		num //= last
	return factors

def find():
	n = int(input())
	a = list(map(int, input().split()))
	dic = {}
	big = 0
	index = -1
	for i in range(n):
		factors = getFactor(a[i])
		for f in factors:
			if f in dic:
				index = max(index, dic[f])
			dic[f] = i
		big = max(big, i - index)
	if big == 1:
		print(-1)
	else:
		print(big)
t = int(input())
for i in range(t):
	find()