from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pref, suf = [0]*n, [0]*n
	for i in range(n):
		pref[i] = a[i]
		suf[n-1-i] = a[n-1-i]
		if i > 0:
			pref[i] = gcd(pref[i], pref[i-1])
			suf[n-1-i] = gcd(suf[n-1-i], suf[n-i])
	if pref[n-1] > 1:
		print(n)
		continue
	ans = 0
	for i in range(n):
		p, s = 0, 0
		if i > 0:
			p = pref[i-1]
		if i+1 < n:
			s = suf[i+1]
		if gcd(p, s) > 1:
			ans += 1
	print(ans)