You are given a sequence $A_1, A_2, \ldots, A_N$. You have to split the array into maximum number of non-empty subarrays such that the gcd of elements of each subarray is equal to 1.

-----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, \ldots, A_N$.

-----Output:-----
For each test case, print a single line containing one integer ― the maximum number of subarrays formed, or $-1$ if the array cannot be split while satisfying the above condition.

-----Constraints-----
- $1 \le T \le 3$
- $1 \le N \le 5 \cdot 10^5$
- $1 \le A_i \le 10^6$ for each valid $i$

-----Sample Input:-----
2
3
2 2 3
4
2 3 3 2

-----Sample Output:-----
1
2

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	i = 0
	while i < len(a):
		if a[i] == 1:
			count += 1
			i += 1
			continue
		curr_gcd = a[i]
		while i < len(a) and curr_gcd != 1:
			curr_gcd = math.gcd(curr_gcd, a[i])
			if curr_gcd == 1:
				count += 1
				i += 1
				break
			i += 1
	print(count)


MOD = 1000000007
MOD2 = 998244353
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
from math import gcd
for _ in range(ii()):
	n = ii()
	l = il()
	c = 0
	g = 0
	for i in range(n):
		g = gcd(g, l[i])
		if g == 1:
			c += 1
			g = 0
	print(c)


import math
T = int(input())
for i in range(T):
	N = int(input())
	lis = list(map(int, input().split()))
	count = 0
	temp = lis[0]
	for j in lis[1:]:
		if temp == 1:
			count += 1
			temp = j
		temp = math.gcd(temp, j)
	if temp == 1:
		count += 1
	print(count)


import math

def solve(arr, n):
	g = 0
	count = 0
	for i in arr:
		g = math.gcd(max(i, g), min(i, g))
		if g == 1:
			g = 0
			count += 1
	if g > 1 and count == 0:
		print(-1)
		return
	print(count)

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