Chef has an array A of length N.

An index i is called *strong* if we can change the [gcd] of the whole array just by changing the value of A_{i}.

Determine the number of *strong* indices in the array.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the size of the array A.
- Second line contains N space separated integers A_{1}, A_{2}, \dots, A_{N} - denoting the array A.

------ Output Format ------ 

For each test case, output the number of strong indices in the array.

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

$1 ≤ T ≤ 5 \cdot 10^{4}$
$2 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases do not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
5 10 20
4
3 5 7 11
4
2 2 2 2

----- Sample Output 1 ------ 
3
0
4

----- explanation 1 ------ 
Test Case $1$: All the indices are strong. 
- For index $1$ you can change the element to $10$ which changes the gcd of the array to $10$. 
- For index $2$ you can change the element to $12$ which changes the gcd of the array to $1$. 
- For index $3$ you can change the element to $12$ which changes the gcd of the array to $1$.

Test Case $2$: No index is strong. If you change any single element, gcd still remains the same.

Test Case $3$: All the indices are strong. You can change any element to $3$. This changes the gcd of the array to $1$.

Source: codechef | Difficulty: MEDIUM
Tags: Number theory

Mathematics


Solutions:
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	a1 = [a[0]]
	b = [a[-1]]
	for i in range(1, n - 1):
		a1.append(math.gcd(a1[i - 1], a[i]))
		b.append(math.gcd(b[i - 1], a[n - 1 - i]))
	if a1[-1] > 1:
		s += 1
	if b[-1] > 1:
		s += 1
	b = b[::-1]
	for i in range(1, n - 1):
		if math.gcd(a1[i - 1], b[i]) > 1:
			s += 1
	print(s)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	al = [a[0]]
	for i in range(1, n):
		al.append(math.gcd(al[-1], a[i]))
	ar = [a[-1]]
	ae = a.copy()
	ae.reverse()
	for i in range(1, n):
		ar.append(math.gcd(ar[-1], ae[i]))
	ar.reverse()
	ans = 0
	for i in range(1, n - 1):
		if math.gcd(al[i - 1], ar[i + 1]) != 1:
			ans += 1
	if ar[1] != 1:
		ans += 1
	if al[-2] != 1:
		ans += 1
	print(ans)


import math as m

def gcdm(a, b):
	if b % a == 0:
		return a
	else:
		return gcdm(b % a, a)
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	hcf = gcdm(A[0], A[1])
	for i in range(2, N):
		hcf = gcdm(hcf, A[i])
	prehcf = [0 for _ in range(N)]
	prehcf[0] = A[0]
	for i in range(1, N):
		prehcf[i] = gcdm(A[i], prehcf[i - 1])
	posthcf = [0 for _ in range(N)]
	posthcf[N - 1] = A[N - 1]
	for i in reversed(range(N - 1)):
		posthcf[i] = gcdm(A[i], posthcf[i + 1])
	if hcf != 1 or (N == 2 and A[0] != 1 and (A[1] != 1)):
		print(N)
	elif N == 2 and (A[0] == 1 or A[1] == 1):
		if A[0] == A[1]:
			print(0)
		else:
			print(1)
	else:
		count = 0
		for i in range(N):
			if i == 0:
				hcf2 = posthcf[1]
			elif i == N - 1:
				hcf2 = prehcf[N - 2]
			else:
				hcf2 = gcdm(prehcf[i - 1], posthcf[i + 1])
			if hcf2 != 1:
				count += 1
		print(count)


import math as m

def gcdm(A, N, k):
	min = A[0] if k != 0 else A[1]
	for i in range(N):
		if A[i] < min and i != k:
			min = A[i]
	ans = 1
	while min != 1:
		flag = 1
		for i in range(N):
			if i != k and A[i] % min != 0:
				flag = 0
				break
		if flag == 1:
			ans = min
			break
		min -= 1
	return ans
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	hcf = m.gcd(A[0], A[1])
	for i in range(2, N):
		hcf = m.gcd(hcf, A[i])
	prehcf = [0 for _ in range(N)]
	prehcf[0] = A[0]
	for i in range(1, N):
		prehcf[i] = m.gcd(A[i], prehcf[i - 1])
	posthcf = [0 for _ in range(N)]
	posthcf[N - 1] = A[N - 1]
	for i in reversed(range(N - 1)):
		posthcf[i] = m.gcd(A[i], posthcf[i + 1])
	if hcf != 1 or (N == 2 and A[0] != 1 and (A[1] != 1)):
		print(N)
	elif N == 2 and (A[0] == 1 or A[1] == 1):
		if A[0] == A[1]:
			print(0)
		else:
			print(1)
	else:
		count = 0
		for i in range(N):
			if i == 0:
				hcf2 = posthcf[1]
			elif i == N - 1:
				hcf2 = prehcf[N - 2]
			else:
				hcf2 = m.gcd(prehcf[i - 1], posthcf[i + 1])
			if hcf2 != 1:
				count += 1
		print(count)


import math
t = int(input())
for _ in range(t):
	p = int(input())
	a = list(map(int, input().split()))
	s = 0
	a1 = [a[0]]
	aa = [a[-1]]
	for i in range(1, p - 1):
		a1.append(math.gcd(a1[i - 1], a[i]))
		aa.append(math.gcd(aa[i - 1], a[p - 1 - i]))
	if a1[-1] > 1:
		s += 1
	if aa[-1] > 1:
		s += 1
	aa = aa[::-1]
	for i in range(1, p - 1):
		if math.gcd(a1[i - 1], aa[i]) > 1:
			s += 1
	print(s)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	A = 0
	a1 = [a[0]]
	aa = [a[-1]]
	for i in range(1, n - 1):
		a1.append(math.gcd(a1[i - 1], a[i]))
		aa.append(math.gcd(aa[i - 1], a[n - 1 - i]))
	if a1[-1] > 1:
		A += 1
	if aa[-1] > 1:
		A += 1
	aa = aa[::-1]
	for i in range(1, n - 1):
		if math.gcd(a1[i - 1], aa[i]) > 1:
			A += 1
	print(A)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	a1 = [a[0]]
	a2 = [a[-1]]
	for i in range(1, n - 1):
		a1.append(math.gcd(a1[i - 1], a[i]))
		a2.append(math.gcd(a2[i - 1], a[n - 1 - i]))
	if a1[-1] > 1:
		ans += 1
	if a2[-1] > 1:
		ans += 1
	a2 = a2[::-1]
	for i in range(1, n - 1):
		if math.gcd(a1[i - 1], a2[i]) > 1:
			ans += 1
	print(ans)


dict1 = {}
from math import gcd

def gcd2(a, b):
	if (a, b) in dict1:
		return dict1[a, b]
	if a % b == 0:
		dict1[a, b] = b
		dict1[b, a] = b
		return b
	else:
		var3 = gcd(b, a % b)
		dict1[a, b] = var3
		dict1[b, a] = var3
		return var3

def GCD(A_s):
	var = A_s[0]
	var3 = [var]
	var4 = [A_s[-1]]
	for i in range(0, len(A_s) - 1):
		var2 = gcd(var, A_s[i + 1])
		var = var2
		var3.append(var2)
	var = A_s[-1]
	for i in range(len(A_s) - 2, -1, -1):
		var2 = gcd(var, A_s[i])
		var = var2
		var4.append(var2)
	return (var3, var4)
T = int(input())
for j in range(0, T):
	N = int(input())
	temp = input()
	A_s = [int(a) for a in temp.split()]
	Strong = 0
	(up, down) = GCD(A_s)
	for i in range(0, N):
		if i == 0 or i == N - 1:
			continue
		if gcd(up[i - 1], down[N - i - 2]) != 1:
			Strong = Strong + 1
	if down[N - 2] != 1:
		Strong = Strong + 1
	if up[N - 2] != 1:
		Strong = Strong + 1
	print(Strong)


from math import gcd
for i 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)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	pre = [l[0]]
	suf = [l[-1]]
	for i in range(1, n - 1):
		pre.append(gcd(pre[i - 1], l[i]))
	for i in range(1, n - 1):
		suf.append(gcd(suf[i - 1], l[n - i - 1]))
	suf.reverse()
	count = 0
	if suf[0] != 1:
		count += 1
	if pre[-1] != 1:
		count += 1
	for i in range(1, n - 1):
		if gcd(pre[i - 1], suf[i]) != 1:
			count += 1
	print(count)


from math import gcd
T = int(input())
for x in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	gc1 = [a[0]]
	gc2 = [a[-1]]
	for i in range(1, n - 1):
		gc1.append(gcd(gc1[i - 1], a[i]))
	for i in range(1, n - 1):
		gc2.append(gcd(gc2[i - 1], a[n - i - 1]))
	gc2.reverse()
	c = 0
	if gc2[0] != 1:
		c += 1
	if gc1[-1] != 1:
		c += 1
	for i in range(1, n - 1):
		if gcd(gc1[i - 1], gc2[i]) != 1:
			c += 1
	print(c)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	gcl = [l[0]]
	gcr = [l[-1]]
	for i in range(1, n - 1):
		gcl.append(math.gcd(gcl[i - 1], l[i]))
	for i in range(1, n - 1):
		gcr.append(math.gcd(gcr[i - 1], l[n - i - 1]))
	gcr.reverse()
	count = 0
	if gcr[0] != 1:
		count += 1
	if gcl[-1] != 1:
		count += 1
	for i in range(1, n - 1):
		if math.gcd(gcl[i - 1], gcr[i]) != 1:
			count += 1
	print(count)


from math import gcd
from sys import stdin
stdint = lambda : int(stdin.readline())
seq = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(stdint()):
	n = stdint()
	nums = seq()
	pre_gcd = [nums[0]] * n
	suf_gcd = [nums[n - 1]] * n
	for i in range(1, n):
		pre_gcd[i] = gcd(pre_gcd[i - 1], nums[i])
	for i in range(n - 2, -1, -1):
		suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i])
	ans = 0
	for i in range(n):
		curr_gcd = 0
		if i == 0:
			curr_gcd = suf_gcd[i + 1]
		elif i == n - 1:
			curr_gcd = pre_gcd[i - 1]
		else:
			curr_gcd = gcd(pre_gcd[i - 1], suf_gcd[i + 1])
		if curr_gcd != 1:
			ans += 1
	print(ans)


import math
case = int(input())
for i in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	prefix = [0 for i in range(n)]
	suffix = [0 for i in range(n)]
	prefix[0] = arr[0]
	suffix[n - 1] = arr[n - 1]
	for i in range(1, n):
		prefix[i] = math.gcd(arr[i], prefix[i - 1])
	for j in reversed(range(n - 1)):
		suffix[j] = math.gcd(arr[j], suffix[j + 1])
	i = 0
	strong = 0
	while i < n:
		if i == 0 and suffix[i + 1] > 1:
			strong += 1
		if i == n - 1 and prefix[n - 2] > 1:
			strong += 1
		if i > 0 and i < n - 1 and (math.gcd(prefix[i - 1], suffix[i + 1]) > 1):
			strong += 1
		i += 1
	print(strong)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def sol(arr, n):
	ans = 0
	(pref_gcd, suff_gcd) = ([0] * n, [0] * n)
	for i in range(n):
		if i == 0:
			pref_gcd[i] = arr[i]
		else:
			pref_gcd[i] = gcd(pref_gcd[i - 1], arr[i])
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suff_gcd[i] = arr[i]
		else:
			suff_gcd[i] = gcd(suff_gcd[i + 1], arr[i])
	for i in range(n):
		curr_gcd = 0
		if i == 0:
			curr_gcd = suff_gcd[i + 1]
		elif i == n - 1:
			curr_gcd = pref_gcd[i - 1]
		else:
			curr_gcd = gcd(pref_gcd[i - 1], suff_gcd[i + 1])
		if curr_gcd != 1:
			ans += 1
	return ans
t = int(input())
while t:
	n = int(input())
	arr_s = input().split()
	arr = []
	for i in arr_s:
		arr.append(int(i))
	print(sol(arr, n))
	t -= 1


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	pre = [0] * n
	suf = [0] * n
	(pre[0], suf[-1]) = (a[0], a[-1])
	for i in range(1, n):
		pre[i] = gcd(pre[i - 1], a[i])
	for j in range(n - 2, -1, -1):
		suf[j] = gcd(suf[j + 1], a[j])
	for k in range(1, n - 1):
		if gcd(pre[k - 1], suf[k + 1]) != 1:
			s += 1
	if suf[1] != 1:
		s += 1
	if pre[n - 2] != 1:
		s += 1
	print(s)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	pre = [0] * n
	suf = [0] * n
	(pre[0], suf[-1]) = (a[0], a[-1])
	for i in range(1, n):
		pre[i] = gcd(pre[i - 1], a[i])
	for j in range(n - 2, -1, -1):
		suf[j] = gcd(suf[j + 1], a[j])
	for k in range(1, n - 1):
		if gcd(pre[k - 1], suf[k + 1]) != 1:
			s += 1
	if suf[1] != 1:
		s += 1
	if pre[n - 2] != 1:
		s += 1
	print(s)


def gcdBuilt(A, B):
	while B:
		(A, B) = (B, A % B)
	return A
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	all_gcd = 0
	for x in A:
		all_gcd = gcdBuilt(x, all_gcd)
	if all_gcd != 1:
		print(N)
	else:
		lp = list()
		lp.append(A[0])
		for i in range(1, N):
			lp.append(gcdBuilt(A[i], lp[i - 1]))
		rp = [0] * N
		rp[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			rp[i] = gcdBuilt(rp[i + 1], A[i])
		cnt = 0
		for i in range(N):
			temp = 0
			if i == 0:
				temp = rp[i + 1]
			elif i == N - 1:
				temp = lp[i - 1]
			else:
				temp = gcdBuilt(lp[i - 1], rp[i + 1])
			if temp != 1:
				cnt += 1
		print(cnt)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pref = a.copy()
	sufi = a.copy()
	for i in range(1, n):
		pref[i] = gcd(pref[i], pref[i - 1])
	for i in range(n - 2, -1, -1):
		sufi[i] = gcd(sufi[i], sufi[i + 1])
	c = 0
	for i in range(n):
		a = 0 if i == 0 else pref[i - 1]
		b = 0 if i == n - 1 else sufi[i + 1]
		if gcd(a, b) > 1:
			c += 1
	print(c)


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	gcd = arr[0]
	gcd_arr_forward = []
	for j in arr:
		gcd = math.gcd(gcd, j)
		gcd_arr_forward.append(gcd)
	gcd_arr_backward = []
	gcd = arr[-1]
	for j in arr[::-1]:
		gcd = math.gcd(gcd, j)
		gcd_arr_backward.append(gcd)
	gcd_arr_backward = gcd_arr_backward[::-1]
	ans = 0
	for j in range(length):
		if j == 0:
			gcd = gcd_arr_backward[j + 1]
		elif j == length - 1:
			gcd = gcd_arr_forward[j - 1]
		else:
			gcd = math.gcd(gcd_arr_forward[j - 1], gcd_arr_backward[j + 1])
		if gcd != 1:
			ans += 1
	print(ans)


from fractions import gcd

def sol(arr, n):
	ans = 0
	(pref_gcd, suff_gcd) = ([0] * n, [0] * n)
	for i in range(n):
		if i == 0:
			pref_gcd[i] = arr[i]
		else:
			pref_gcd[i] = gcd(pref_gcd[i - 1], arr[i])
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			suff_gcd[i] = arr[i]
		else:
			suff_gcd[i] = gcd(suff_gcd[i + 1], arr[i])
	for i in range(n):
		curr_gcd = 0
		if i == 0:
			curr_gcd = suff_gcd[i + 1]
		elif i == n - 1:
			curr_gcd = pref_gcd[i - 1]
		else:
			curr_gcd = gcd(pref_gcd[i - 1], suff_gcd[i + 1])
		if curr_gcd != 1:
			ans += 1
	return ans
t = int(input())
while t:
	n = int(input())
	arr_s = input().split()
	arr = []
	for i in arr_s:
		arr.append(int(i))
	print(sol(arr, n))
	t -= 1


import math
t = int(input())
while t > 0:
	n = int(input())
	array = list(map(int, input().split(' ')[:n]))
	curr_pre_gcd = array[0]
	prefix_gcd = [array[0]]
	curr_suf_gcd = array[n - 1]
	suffix_gcd = [array[n - 1]]
	for i in range(1, n):
		curr_pre_gcd = math.gcd(curr_pre_gcd, array[i])
		prefix_gcd.append(curr_pre_gcd)
	for i in range(n - 2, -1, -1):
		curr_suf_gcd = math.gcd(curr_suf_gcd, array[i])
		suffix_gcd.append(curr_suf_gcd)
	suffix_gcd = suffix_gcd[::-1]
	if suffix_gcd[0] != 1:
		print(n)
	else:
		count = 0
		for i in range(n):
			if i == 0:
				if suffix_gcd[1] != 1:
					count += 1
			elif i == n - 1:
				if prefix_gcd[n - 2] != 1:
					count += 1
			elif math.gcd(prefix_gcd[i - 1], suffix_gcd[i + 1]) != 1:
				count += 1
		print(count)
	t -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	hcf = arr[0]
	while i < n:
		hcf = math.gcd(hcf, arr[i])
		i = i + 1
	prefix_gcd = [1] * n
	suffix_gcd = [1] * n
	i = 1
	prefix_gcd[0] = arr[0]
	suffix_gcd[n - 1] = arr[n - 1]
	while i < n:
		prefix_gcd[i] = math.gcd(prefix_gcd[i - 1], arr[i])
		suffix_gcd[n - i - 1] = math.gcd(suffix_gcd[n - i], arr[n - i - 1])
		i = i + 1
	count = 0
	if prefix_gcd[n - 2] > 1:
		count = count + 1
	if suffix_gcd[1] > 1:
		count = count + 1
	i = 1
	while i < n - 1:
		if math.gcd(prefix_gcd[i - 1], suffix_gcd[i + 1]) > 1:
			count = count + 1
		i = i + 1
	if hcf > 1:
		print(n)
	else:
		print(count)


import math
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	(pre, suf) = ([0] * n, [0] * n)
	for i in range(0, n):
		pre[i] = arr[i]
		suf[n - 1 - i] = arr[n - 1 - i]
		if i > 0:
			pre[i] = math.gcd(pre[i], pre[i - 1])
			suf[n - 1 - i] = math.gcd(suf[n - 1 - i], suf[n - i])
	if pre[n - 1] > 1:
		print(n)
		continue
	SE = 0
	for i in range(n):
		(p, s) = (0, 0)
		if i > 0:
			p = pre[i - 1]
		if i + 1 < n:
			s = suf[i + 1]
		if math.gcd(p, s) > 1:
			SE += 1
	print(SE)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p_g = [0] * n
	p_g[0] = l[0]
	for i in range(1, n):
		p_g[i] = gcd(p_g[i - 1], l[i])
	s_g = [0] * n
	s_g[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		s_g[i] = gcd(s_g[i + 1], l[i])
	st = 0
	for i in range(0, n):
		if i == 0:
			if s_g[1] > 1:
				st += 1
		elif i == n - 1:
			if p_g[n - 2] > 1:
				st += 1
		elif gcd(s_g[i + 1], p_g[i - 1]) > 1:
			st += 1
	print(st)


from bisect import bisect_left, bisect_right
from email import header
from heapq import heapify, heappush, heappop
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
from tkinter import N
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
for _ in range(ii()):
	n = ii()
	arr = il()
	ans = 0
	pre = [arr[0]]
	suf = [-1] * n
	suf[-1] = arr[-1]
	for l in range(1, n):
		pre.append(gcd(pre[-1], arr[l]))
	for l in range(n - 2, -1, -1):
		suf[l] = gcd(suf[l + 1], arr[l])
	for k in range(1, n - 1):
		if gcd(pre[k - 1], suf[k + 1]) != 1:
			ans += 1
	if suf[1] != 1:
		ans += 1
	if pre[-2] != 1:
		ans += 1
	print(ans)


inty = lambda : int(input())
stringy = lambda : input().strip()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
from math import gcd
T = inty()
for i in range(T):
	n = inty()
	alist = listy()
	count = 0
	prefix = [0] * n
	prefix[0] = alist[0]
	for i in range(1, n):
		prefix[i] = gcd(prefix[i - 1], alist[i])
	suffix = [0] * n
	suffix[-1] = alist[-1]
	for i in range(n - 2, -1, -1):
		suffix[i] = gcd(suffix[i + 1], alist[i])
	for i in range(1, n - 1):
		if gcd(prefix[i - 1], suffix[i + 1]) != 1:
			count += 1
	if suffix[1] != 1:
		count += 1
	if prefix[n - 2] != 1:
		count += 1
	print(count)


import math
T = int(input())
while T:
	N = int(input())
	L = list(map(int, input().split()))
	prefix = list()
	prefix.append(L[0])
	for i in range(1, N):
		prefix.append(math.gcd(prefix[i - 1], L[i]))
	suffix = [0] * N
	suffix[N - 1] = L[N - 1]
	for i in range(N - 2, -1, -1):
		suffix[i] = math.gcd(L[i], suffix[i + 1])
	strong = 0
	for i in range(0, N):
		if i == 0:
			if suffix[1] > 1:
				strong += 1
		elif i == N - 1:
			if prefix[N - 2] > 1:
				strong += 1
		elif math.gcd(suffix[i + 1], prefix[i - 1]) > 1:
			strong += 1
	print(strong)
	T = T - 1


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
for t in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().strip().split()))
	pref_gcd = []
	suff_gcd = []
	pref_gcd.append(a[0])
	suff_gcd.append(a[n - 1])
	for i in range(1, n):
		pref_gcd.append(gcd(pref_gcd[i - 1], a[i]))
		suff_gcd.append(gcd(suff_gcd[i - 1], a[n - 1 - i]))
	suff_gcd = suff_gcd[::-1]
	if pref_gcd[n - 1] == 1:
		ans = 0
		for i in range(n):
			if i == 0:
				curr_gcd = suff_gcd[i + 1]
			elif i == n - 1:
				curr_gcd = pref_gcd[n - 2]
			else:
				curr_gcd = gcd(pref_gcd[i - 1], suff_gcd[i + 1])
			if curr_gcd > 1:
				ans += 1
	else:
		ans = n
	print(ans)


import math
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	prefix = list()
	prefix.append(l[0])
	for i in range(1, n):
		prefix.append(math.gcd(prefix[i - 1], l[i]))
	suffix = [0] * n
	suffix[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = math.gcd(l[i], suffix[i + 1])
	strong = 0
	for i in range(0, n):
		if i == 0:
			if suffix[1] > 1:
				strong += 1
		elif i == n - 1:
			if prefix[n - 2] > 1:
				strong += 1
		elif math.gcd(suffix[i + 1], prefix[i - 1]) > 1:
			strong += 1
	print(strong)
	t = t - 1


import math
t = int(input())
for j in range(t):
	n = int(input())
	l = map(int, input().split())
	l = list(l)
	c = 0
	pre = [0] * n
	suf = [0] * n
	(pre[0], suf[-1]) = (l[0], l[-1])
	for i in range(1, n):
		pre[i] = math.gcd(pre[i - 1], l[i])
	for i in range(n - 2, -1, -1):
		suf[i] = math.gcd(suf[i + 1], l[i])
	for i in range(1, n - 1):
		if math.gcd(pre[i - 1], suf[i + 1]) != 1:
			c += 1
	if suf[1] != 1:
		c += 1
	if pre[n - 2] != 1:
		c += 1
	print(c)


def gcd(a, b):
	if a == 0:
		return abs(b)
	else:
		return gcd(b % a, a)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(pre, suf) = ([0] * n, [0] * n)
	for i in range(n):
		pre[i] = a[i]
		suf[n - i - 1] = a[n - i - 1]
		if i > 0:
			pre[i] = gcd(pre[i - 1], pre[i])
			suf[n - i - 1] = gcd(suf[n - i], suf[n - i - 1])
	if pre[n - 1] > 1:
		print(n)
		continue
	res = 0
	for i in range(n):
		(p, s) = (0, 0)
		if i > 0:
			p = pre[i - 1]
		if i < n - 1:
			s = suf[i + 1]
		if gcd(p, s) > 1:
			res += 1
	print(res)


def gcd(A, B):
	if A == 0:
		return B
	return gcd(B % A, A)
T = int(input())
for _ in range(T):
	N = int(input())
	ARR = list(map(int, input().split()))
	suf = list()
	pre = list()
	res = ARR[0]
	pre.append(res)
	for i in range(1, N - 1):
		res = gcd(res, ARR[i])
		pre.append(res)
	res = ARR[N - 1]
	suf.append(res)
	for i in range(N - 2, -1, -1):
		res = gcd(res, ARR[i])
		suf.append(res)
	suf = suf[::-1]
	res = 0
	for i in range(N):
		if i == 0:
			if suf[1] != 1:
				res += 1
		elif i == N - 1:
			if pre[i - 1] != 1:
				res += 1
		elif gcd(pre[i - 1], suf[i + 1]) != 1:
			res += 1
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [0] * n
	suffix = [0] * n
	ans = 0
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = math.gcd(prefix[i - 1], arr[i])
	suffix[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = math.gcd(suffix[i + 1], arr[i])
	for i in range(n):
		if i == 0:
			x = suffix[i + 1]
		elif i == n - 1:
			x = prefix[i - 1]
		else:
			x = math.gcd(suffix[i + 1], prefix[i - 1])
		if x > 1:
			ans += 1
	print(ans)


from math import gcd
t = int(input())
while t > 0:
	n = int(input())
	ai = input().split()
	an = []
	for i in ai:
		an.append(int(i))
	prefix = []
	suffix = []
	(prefix, suffix) = ([0] * n, [0] * n)
	for i in range(n):
		prefix[i] = an[i]
		suffix[n - 1 - i] = an[n - 1 - i]
		if i > 0:
			prefix[i] = gcd(prefix[i], prefix[i - 1])
			suffix[n - 1 - i] = gcd(suffix[n - 1 - i], suffix[n - i])
	ans = 0
	for i in range(n):
		(pr, su) = (0, 0)
		if i > 0:
			pr = prefix[i - 1]
		if i + 1 < n:
			su = suffix[i + 1]
		if gcd(pr, su) > 1:
			ans += 1
	print(ans)
	t -= 1


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(fdp, rdp) = ([arr[0] for i in range(n)], [arr[-1] for i in range(n)])
	for i in range(1, n):
		fdp[i] = gcd(arr[i], fdp[i - 1])
		rdp[n - i - 1] = gcd(arr[n - i - 1], rdp[n - i])
	goa = gcd(fdp[-1], arr[-1])
	if goa != 1:
		print(n)
	else:
		ans = 0
		if rdp[1] != 1:
			ans += 1
		if fdp[-2] != 1:
			ans += 1
		for i in range(1, n - 1):
			if gcd(fdp[i - 1], rdp[i + 1]) != 1:
				ans += 1
		print(ans)


def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a % b)

def FillPrefixSuffix(prefix, arr, suffix, n):
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = GCD(prefix[i - 1], arr[i])
	suffix[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = GCD(suffix[i + 1], arr[i])
T = int(input())
for t in range(T):
	prefix = []
	suffix = []
	c = 0
	a = 0
	b = 0
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(n + 1):
		prefix.append(0)
		suffix.append(0)
	FillPrefixSuffix(prefix, arr, suffix, n)
	for i in range(n):
		if i - 1 >= 0:
			a = prefix[i - 1]
		else:
			a = 0
		if i + 1 < n:
			b = suffix[i + 1]
		else:
			b = 0
		if GCD(a, b) > 1:
			c = c + 1
	print(c)


import math as m
for i in range(int(input())):
	num = int(input())
	lst = list(map(int, input().split()))[:num]
	pre = [lst[0]]
	suf = [0] * num
	suf[num - 1] = lst[num - 1]
	for i in range(1, num):
		pre.append(m.gcd(pre[i - 1], lst[i]))
	for i in range(num - 2, -1, -1):
		suf[i] = m.gcd(suf[i + 1], lst[i])
	(a, b, ans) = (0, 0, 0)
	for i in range(num):
		a = pre[i - 1] if i - 1 >= 0 else 0
		b = suf[i + 1] if i + 1 < num else 0
		if m.gcd(a, b) > 1:
			ans += 1
	print(ans)


def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	prefix_gcd = [0] * n
	prefix_gcd[0] = arr[0]
	for i in range(1, n):
		prefix_gcd[i] = find_gcd(arr[i], prefix_gcd[i - 1])
	suffix_gcd = [0] * n
	suffix_gcd[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		suffix_gcd[i] = find_gcd(arr[i], suffix_gcd[i + 1])
	ans = 0
	for i in range(n):
		if i == 0 and suffix_gcd[1] > 1:
			ans += 1
		elif i == n - 1 and prefix_gcd[n - 2] > 1:
			ans += 1
		elif i < n - 1 and find_gcd(prefix_gcd[i - 1], suffix_gcd[i + 1]) > 1:
			ans += 1
	print(ans)
	t -= 1


import math

def jeevi(laddu, rudra, loya, maruti, ninja):
	if laddu == 0:
		return maruti[rudra + 1]
	if rudra == ninja - 1:
		return loya[laddu - 1]
	return math.gcd(loya[laddu - 1], maruti[rudra + 1])

def din(loya, arya, maruti, ninja):
	loya[0] = arya[0]
	for i in range(ninja):
		loya[i] = math.gcd(loya[i - 1], arya[i])
	maruti[ninja - 1] = arya[ninja - 1]
	for i in range(ninja - 2, -1, -1):
		maruti[i] = math.gcd(maruti[i + 1], arya[i])
test = int(input())
for i in range(test):
	andhra = int(input())
	sas = [int(i) for i in input().split()]
	loya = []
	maruti = []
	for i in range(andhra):
		loya.append(0)
		maruti.append(0)
	din(loya, sas, maruti, andhra)
	kittu = 0
	for i in range(andhra):
		if jeevi(i, i, loya, maruti, andhra) > 1:
			kittu = kittu + 1
	print(kittu)


from math import gcd
g = int(input())
for i in range(g):
	n = int(input())
	llp = list(map(int, input().split()))
	pre = [1 for t in range(n)]
	pre[0] = llp[0]
	for j in range(1, n):
		pre[j] = gcd(pre[j - 1], llp[j])
	suf = [1 for x in range(n)]
	suf[n - 1] = llp[n - 1]
	for j in reversed(range(n - 1)):
		suf[j] = gcd(suf[j + 1], llp[j])
	a = 0
	for q in range(n):
		if q == 0:
			if suf[1] > 1:
				a += 1
		elif q == n - 1:
			if pre[n - 2] > 1:
				a += 1
		elif gcd(suf[q + 1], pre[q - 1]) > 1:
			a += 1
	print(a)


import math
t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))[:n]
	prefixgcd = [0] * n
	suffixgcd = [0] * n
	prefixgcd[0] = ar[0]
	for i in range(n):
		prefixgcd[i] = math.gcd(prefixgcd[i - 1], ar[i])
	suffixgcd[n - 1] = ar[n - 1]
	for i in range(n - 2, -1, -1):
		suffixgcd[i] = math.gcd(suffixgcd[i + 1], ar[i])
	ans = 0
	for i in range(1, n - 1):
		if math.gcd(prefixgcd[i - 1], suffixgcd[i + 1]) > 1:
			ans += 1
	for i in range(n):
		if i == 0 and suffixgcd[1] > 1:
			ans += 1
		if i == n - 1 and prefixgcd[n - 2] > 1:
			ans += 1
	print(ans)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	front = [A[0]]
	reverse = [A[-1]]
	count = 0
	res = gcd(A[0], A[1])
	for i in range(2, N):
		front.append(res)
		res = gcd(res, A[i])
	res = gcd(A[-1], A[-2])
	for i in range(N - 3, -1, -1):
		reverse.append(res)
		res = gcd(res, A[i])
	for i in range(N):
		if i == 0:
			if reverse[-1] != 1:
				count += 1
		elif i == N - 1:
			if front[-1] != 1:
				count += 1
		elif gcd(reverse[N - 2 - i], front[i - 1]) != 1:
			count += 1
	print(count)


import math

def fpr(pr, ar, su, n):
	pr[0] = ar[0]
	for i in range(1, n):
		pr[i] = math.gcd(pr[i - 1], ar[i])
	su[n - 1] = ar[n - 1]
	for i in range(n - 2, -1, -1):
		su[i] = math.gcd(su[i + 1], ar[i])

def gor(o, p, pr, su, n):
	if o == 0:
		return su[p + 1]
	if p == n - 1:
		return pr[o - 1]
	return math.gcd(pr[o - 1], su[p + 1])

def sol():
	n = int(input())
	ar = list(map(int, input().split()))
	pr = [0] * n
	su = [0] * n
	fpr(pr, ar, su, n)
	ans = 0
	for i in range(n):
		if gor(i, i, pr, su, n) > 1:
			ans += 1
	print(ans)
for i in range(int(input())):
	sol()


from math import gcd
from functools import reduce

def fgcd(list):
	x = reduce(gcd, list)
	return x
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l1 = l.copy()
	pregcd = []
	sufgcd = []
	pregcd.append(l[0])
	for i in range(1, n):
		ans1 = gcd(pregcd[i - 1], l[i])
		pregcd.append(ans1)
	l1.reverse()
	sufgcd.append(l1[0])
	for i in range(1, n):
		ans1 = gcd(sufgcd[i - 1], l1[i])
		sufgcd.append(ans1)
	sufgcd.reverse()
	co = 0
	for i in range(n):
		if i == 0 and sufgcd[1] > 1:
			co = co + 1
		elif i == n - 1 and pregcd[n - 2] > 1:
			co = co + 1
		elif i != 0 and i != n - 1 and (gcd(pregcd[i - 1], sufgcd[i + 1]) > 1):
			co = co + 1
		else:
			pass
	print(co)


import math
z = int(input())
for i in range(z):
	n = int(input())
	l = list(map(int, input().split()))
	prefix = [0] * n
	prefix[0] = l[0]
	for i in range(1, len(l)):
		prefix[i] = math.gcd(prefix[i - 1], l[i])
	suffix = [0] * n
	suffix[n - 1] = l[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = math.gcd(suffix[i + 1], l[i])
	count = 0
	if suffix[1] != 1:
		count = count + 1
	if prefix[n - 2] != 1:
		count += 1
	for i in range(1, n - 1):
		if math.gcd(prefix[i - 1], suffix[i + 1]) != 1:
			count += 1
	print(count)


import math
from array import *

def gcd(x, y):
	return math.gcd(x, y)

def fill(pre, suf, lst, n, suf2):
	pre.append(lst[0])
	lst2 = []
	for ele in range(n - 1, -1, -1):
		lst2.append(lst[ele])
	suf.append(lst2[0])
	for i in range(1, n):
		pre.append(gcd(pre[i - 1], lst[i]))
	for i in range(1, n):
		suf.append(gcd(suf[i - 1], lst2[i]))
	for i in range(n - 1, -1, -1):
		suf2.append(suf[i])

def gcdcount(p, r, pre, suf, n):
	if p == 0:
		return suf[r + 1]
	if r == n - 1:
		return pre[p - 1]
	return gcd(pre[p - 1], suf[r + 1])
for _ in range(int(input())):
	n = int(input())
	lst = [int(ele) for ele in input().split(' ')]
	pre = []
	suf = []
	suf2 = []
	fill(pre, suf, lst, n, suf2)
	ans = 0
	for i in range(0, n):
		if gcdcount(i, i, pre, suf2, n) > 1:
			ans = ans + 1
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(pref, suff) = ([0 for i in range(n)] for i in range(2))
	pref[0] = arr[0]
	suff[-1] = arr[-1]
	for i in range(1, n):
		pref[i] = gcd(pref[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		suff[i] = gcd(suff[i + 1], arr[i])
	strong = 0
	if suff[1] > 1:
		strong += 1
	if pref[n - 2] > 1:
		strong += 1
	for i in range(1, n - 1):
		if gcd(pref[i - 1], suff[i + 1]) > 1:
			strong += 1
	print(strong)


import math

def first(suffix, preffix, arr, n):
	preffix[0] = arr[0]
	for j in range(1, n - 1):
		preffix[j] = math.gcd(preffix[j - 1], arr[j])
	suffix[n - 1] = arr[n - 1]
	for k in range(n - 2, 0, -1):
		suffix[k] = math.gcd(suffix[k + 1], arr[k])

def second(l, r, preffix, suffix, n):
	if l == 0:
		return suffix[r + 1]
	if r == n - 1:
		return preffix[l - 1]
	return math.gcd(preffix[l - 1], suffix[r + 1])
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(suffix, preffix) = ([None] * n, [None] * n)
	first(suffix, preffix, arr, n)
	ans = 0
	for i in range(n):
		if second(i, i, preffix, suffix, n) > 1:
			ans += 1
	print(ans)


def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a % b)
t = int(input())
for _ in range(t):
	ans = 0
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [0] * n
	suffix = [0] * n
	prefix[0] = arr[0]
	for i in range(1, n):
		prefix[i] = GCD(prefix[i - 1], arr[i])
	suffix[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		suffix[i] = GCD(suffix[i + 1], arr[i])
	for i in range(1, n - 1):
		if GCD(prefix[i - 1], suffix[i + 1]) > 1:
			ans += 1
	if GCD(0, suffix[1]) > 1:
		ans += 1
	if GCD(prefix[n - 2], 0) > 1:
		ans += 1
	print(ans)


import math

def newarray(pre, nums, suff, n):
	pre[0] = nums[0]
	for i in range(1, n):
		pre[i] = math.gcd(pre[i - 1], nums[i])
	suff[-1] = nums[-1]
	for i in range(n - 2, -1, -1):
		suff[i] = math.gcd(suff[i + 1], nums[i])
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().strip().split()))
	pre = [0] * n
	suff = [0] * n
	newarray(pre, nums, suff, n)
	count = 0
	for i in range(n):
		if i == 0 and suff[i + 1] > 1:
			count += 1
		elif i == n - 1 and pre[n - 2] > 1:
			count += 1
		elif i != n - 1 and math.gcd(pre[i - 1], suff[i + 1]) > 1:
			count += 1
	print(count)


from math import gcd

def func(k, l, m, o, n):
	if k == 0:
		return o[l + 1]
	if l == n - 1:
		return m[k - 1]
	return gcd(m[k - 1], o[l + 1])

def func2(m, arr, o, n):
	m[0] = arr[0]
	for i in range(1, n):
		m[i] = gcd(m[i - 1], arr[i])
	o[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		o[i] = gcd(o[i + 1], arr[i])
for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	p = [0] * N
	s = [0] * N
	d = func2(p, A, s, N)
	a = 0
	for i in range(N):
		if func(i, i, p, s, N) > 1:
			a = a + 1
	print(a)


import math
T = int(input())
while T:
	n = int(input())
	l = list(map(int, input().split()))
	till = []
	after = []
	till.append(l[0])
	after.append(l[-1])
	for i in range(1, n):
		till.append(math.gcd(till[i - 1], l[i]))
	for i in range(n - 2, -1, -1):
		after.append(math.gcd(after[n - i - 2], l[i]))
	after = after[::-1]
	str = 0
	for i in range(n):
		currgcd = 0
		if i == 0:
			currgcd = after[1]
		elif i == n - 1:
			currgcd = till[n - 2]
		else:
			currgcd = math.gcd(till[i - 1], after[i + 1])
		if currgcd > 1:
			str += 1
	print(str)
	T = T - 1


from math import gcd
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	prefix = [1 for k in range(n)]
	prefix[0] = arr[0]
	for j in range(1, n):
		prefix[j] = gcd(prefix[j - 1], arr[j])
	suffix = [1 for x in range(n)]
	suffix[n - 1] = arr[n - 1]
	for j in reversed(range(n - 1)):
		suffix[j] = gcd(suffix[j + 1], arr[j])
	x = 0
	for k in range(n):
		if k == 0:
			if suffix[1] > 1:
				x += 1
		elif k == n - 1:
			if prefix[n - 2] > 1:
				x += 1
		elif gcd(suffix[k + 1], prefix[k - 1]) > 1:
			x += 1
	print(x)


import math
rick = int(input())
for _ in range(rick):
	n = int(input())
	a = list(map(int, input().split()))
	pref = []
	for i in range(n):
		pref.append(0)
	pref[0] = a[0]
	for i in range(1, n, 1):
		pref[i] = math.gcd(pref[i - 1], a[i])
	suff = []
	for i in range(n):
		suff.append(0)
	suff[n - 1] = a[n - 1]
	for i in range(n - 2, 0, -1):
		suff[i] = math.gcd(suff[i + 1], a[i])
	str_ele = 0
	for j in range(n):
		if j - 1 >= 0:
			final = pref[j - 1]
		else:
			final = 0
		if j + 1 < n:
			lower = suff[j + 1]
		else:
			lower = 0
		if math.gcd(final, lower) > 1:
			str_ele += 1
	print(str_ele)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pre = [1 for i in range(n)]
	pre[0] = a[0]
	for i in range(1, n):
		pre[i] = gcd(pre[i - 1], a[i])
	suf = [1 for i in range(n)]
	suf[n - 1] = a[n - 1]
	for i in reversed(range(n - 1)):
		suf[i] = gcd(suf[i + 1], a[i])
	ans = 0
	for i in reversed(range(n)):
		if i == 0:
			if suf[1] > 1:
				ans += 1
		elif i == n - 1:
			if pre[n - 2] > 1:
				ans += 1
		elif gcd(suf[i + 1], pre[i - 1]) > 1:
			ans += 1
	print(ans)