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

Difficulty: interview

Starter code:

Solutions:
'''input
2
3
2 2 3
4
2 3 3 2
'''
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
    # print(i)
    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()