You are given an array $a$ consisting of $n$ integers $a_1, a_2, \ldots, a_n$. Friends asked you to make the greatest common divisor (GCD) of all numbers in the array equal to $1$. In one operation, you can do the following:

Select an arbitrary index in the array $1 \leq i \leq n$;

Make $a_i = \gcd(a_i, i)$, where $\gcd(x, y)$ denotes the GCD of integers $x$ and $y$. The cost of such an operation is $n - i + 1$.

You need to find the minimum total cost of operations we need to perform so that the GCD of the all array numbers becomes equal to $1$.


-----Input-----

Each test consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 5000$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 20$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.


-----Output-----

For each test case, output a single integer — the minimum total cost of operations that will need to be performed so that the GCD of all numbers in the array becomes equal to $1$.

We can show that it's always possible to do so.


-----Examples-----

Input
9
1
1
1
2
2
2 4
3
3 6 9
4
5 10 15 20
5
120 60 80 40 80
6
150 90 180 120 60 30
6
2 4 6 9 12 18
6
30 60 90 120 125 125
Output
0
1
2
2
1
3
3
0
1


-----Note-----

In the first test case, the GCD of the entire array is already equal to $1$, so there is no need to perform operations.

In the second test case, select $i = 1$. After this operation, $a_1 = \gcd(2, 1) = 1$. The cost of this operation is $1$.

In the third test case, you can select $i = 1$, after that the array $a$ will be equal to $[1, 4]$. The GCD of this array is $1$, and the total cost is $2$.

In the fourth test case, you can select $i = 2$, after that the array $a$ will be equal to $[3, 2, 9]$. The GCD of this array is $1$, and the total cost is $2$.

In the sixth test case, you can select $i = 4$ and $i = 5$, after that the array $a$ will be equal to $[120, 60, 80, 4, 5]$. The GCD of this array is $1$, and the total cost is $3$.

Source: codeforces | Difficulty: EASY
Tags: Constructive algorithms

Combinatorics

Implementation

Complete search

Number theory

Mathematics


Solutions:
import sys
from math import gcd
rd = sys.stdin.readline
for _ in range(int(rd())):
	n = int(rd())
	l = list(map(int, rd().split()))
	g = l[0]
	for i in l:
		g = gcd(i, g)
	if g == 1:
		print(0)
	else:
		x = gcd(l[-1], n)
		try:
			y = gcd(l[-2], n - 1)
		except:
			pass
		if gcd(g, x) == 1:
			print(1)
		elif gcd(g, y) == 1:
			print(2)
		else:
			print(3)


import sys
input = sys.stdin.readline
from math import ceil, comb, gcd
list_input = lambda x=int: list(map(x, input().strip().split()))
mult_input = lambda x=int: map(x, input().strip().split())

def solve():
	n = int(input())
	a = list_input()
	k = a[0]
	for i in a:
		k = gcd(k, i)
	if k == 1:
		return 0
	l = a[-1]
	x = gcd(l, n)
	k1 = gcd(k, x)
	if k1 == 1:
		return 1
	l2 = a[-2]
	x = gcd(l2, n - 1)
	k = gcd(x, k)
	if k == 1:
		return 2
	return 3
for _ in range(int(input())):
	print(solve())


import math

def fuc(n, lis):
	g = lis[0]
	for i in lis:
		g = math.gcd(g, i)
	if g == 1:
		return 0
	if math.gcd(n, g) == 1:
		return 1
	elif math.gcd(n - 1, g) == 1:
		return 2
	else:
		return 3
n = int(input())
lis = []
res = []
for _ in range(n):
	i = int(input())
	lis = list(map(int, input().split()))
	res.append(fuc(i, lis))
for re in res:
	print(re)


def main():

	def main():
		T = readInt()
		for _ in range(T):
			N = readInt()
			A = readInts()
			print(solve(A, N))

	def solve(A, N):
		g = 0
		for x in A:
			g = gcd(g, x)
		if g == 1:
			return 0
		if gcd(g, gcd(A[-1], N)) == 1:
			return 1
		if gcd(g, gcd(A[-2], N - 1)) == 1:
			return 2
		if gcd(gcd(g, gcd(A[-1], N)), gcd(A[-2], N - 1)) == 1:
			return 3
		else:
			1 / 0
	main()
MOD = 10 ** 9 + 7
import sys
from math import ceil, gcd
from itertools import product
from collections import deque, Counter, defaultdict
from bisect import bisect_left, bisect_right, insort
from pprint import pprint
read = sys.stdin.readline
readString = lambda : read().strip()
readInt = lambda : int(readString())
readStrings = lambda delim=' ': readString().split(delim)
readInts = lambda delim=' ': [int(_) for _ in readStrings(delim)]
main()


import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	gd = lst[0]
	for i in lst[1:]:
		gd = math.gcd(gd, i)
	if gd == 1:
		print(0)
	elif math.gcd(gd, n) == 1:
		print(1)
	elif math.gcd(gd, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import gcd
t = int(input())
answers = []
for i in range(t):
	n = int(input())
	list = [int(i) for i in input().split()]
	answer = 0
	g = 0
	for i in range(len(list)):
		g = gcd(g, list[i])
	if g == 1:
		answer = 0
	elif gcd(g, gcd(n, list[n - 1])) == 1:
		answer = 1
	elif gcd(g, gcd(n - 1, list[n - 2])) == 1:
		answer = 2
	else:
		answer = 3
	answers.append(answer)
for i in answers:
	print(i)


import sys
import math

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	g = a[0]
	for i in range(1, n):
		g = math.gcd(g, a[i])
	ans = 3
	if math.gcd(g, n - 1) == 1:
		ans = 2
	if math.gcd(g, n) == 1:
		ans = 1
	if g == 1:
		ans = 0
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from math import gcd

def GCD(a):
	x = a[0]
	for y in a[1:]:
		x = gcd(x, y)
	return x
for s in [*open(0)][2::2]:
	a = [*map(int, s.split())]
	if GCD(a) == 1:
		print(0)
	elif GCD(a[:-1] + [gcd(a[-1], len(a))]) == 1:
		print(1)
	elif GCD(a[:-2] + [gcd(a[-2], len(a) - 1)] + a[-1:]) == 1:
		print(2)
	else:
		print(3)


import math
import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

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

def solve():
	n = readInt()
	arr = readList()
	v = arr[0]
	for i in range(1, n):
		v = math.gcd(v, arr[i])
	if v == 1:
		return 0
	(v1, v2) = (math.gcd(v, n), math.gcd(v, n - 1))
	if v1 == 1:
		return 1
	elif v2 == 1:
		return 2
	else:
		return 3
for _ in range(int(input())):
	print(solve())


import sys
import sys
import threading
from math import *
from bisect import *
from collections import *
from heapq import *
from functools import lru_cache

def gl():
	return list(map(int, input().split()))

def gi():
	return int(input())

def gc():
	return input()
dd = defaultdict
dq = deque
hp = heappush
hpp = heappop
hpf = heapify

def solution():
	n = gi()
	arr = gl()
	cur = arr[0]
	for i in arr:
		cur = gcd(i, cur)
	if cur == 1:
		return print(0)
	if gcd(n, cur) == 1:
		return print(1)
	if gcd(n - 1, cur) == 1:
		return print(2)
	return print(3)

def main():
	t = gi()
	for i in range(t):
		solution()
main()


import sys
from math import gcd
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	b = []
	for i in a:
		g = gcd(g, i)
		b.append(g)
	if g == 1:
		print(0)
		continue
	if n == 1:
		print(1)
		continue
	if n == 2:
		if gcd(gcd(n, a[n - 1]), a[n - 2]) == 1:
			print(1)
		elif gcd(gcd(n - 1, a[n - 2]), a[n - 1]) == 1:
			print(2)
		else:
			print(3)
		continue
	if gcd(gcd(n, a[n - 1]), b[n - 2]) == 1:
		print(1)
	elif gcd(gcd(gcd(n - 1, a[n - 2]), b[n - 3]), a[n - 1]) == 1:
		print(2)
	else:
		print(3)


k = int(input())
result = []

def gcd(x, y):
	if x < y:
		(x, y) = (y, x)
	while y != 0:
		r = x % y
		x = y
		y = r
	return x
for i in range(k):
	n = int(input())
	list = [int(x) for x in input().split()]
	g = list[0]
	for j in range(0, n):
		g = gcd(g, list[j])
		if g == 1:
			cost = 0
			result.append(cost)
			break
	if g != 1:
		if gcd(g, n) == 1:
			cost = 1
			result.append(cost)
		elif gcd(g, n - 1) == 1:
			cost = 2
			result.append(cost)
		else:
			cost = 3
			result.append(cost)
for i in range(len(result)):
	print(result[i])


from math import gcd
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for i in a:
		g = gcd(g, i)
	if g == 1:
		print(0)
	elif gcd(g, n) == 1:
		print(1)
	elif gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)


import math
import functools

def gcd_list(l):
	return functools.reduce(math.gcd, l)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if gcd_list(a) == 1:
		print(0)
	else:
		b = gcd_list(a)
		if math.gcd(b, n) == 1:
			print(1)
		elif math.gcd(b, n - 1) == 1:
			print(2)
		else:
			print(3)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = 0
	for i in l:
		d = math.gcd(d, i)
	if d == 1:
		print(0)
	elif math.gcd(d, n) == 1:
		print(1)
	elif math.gcd(d, n - 1) == 1:
		print(2)
	else:
		print(3)


import math
t = int(input())
for t in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = arr[0]
	if n == 1:
		if arr[0] == 1:
			print(0)
		else:
			print(1)
	else:
		for i in range(1, n):
			x = math.gcd(arr[i], x)
		if x == 1:
			print(0)
		elif math.gcd(x, n) == 1:
			print(1)
		elif math.gcd(x, n - 1) == 1:
			print(2)
		else:
			print(3)


fl = 'input.txt'

def gcd(my_list):
	result = my_list[0]
	for x in my_list[1:]:
		if result < x:
			temp = result
			result = x
			x = temp
		while x != 0:
			temp = x
			x = result % x
			result = temp
	return result
import sys
import math
flh = sys.stdin
test_cases = int(flh.readline())
res = []
for case in range(test_cases):
	n = int(flh.readline())
	a = [int(x) for x in flh.readline().strip().split()]
	gcd1 = gcd(a)
	if gcd1 == 1:
		print(0)
	elif gcd([gcd1, a[n - 1], n]) == 1:
		print(1)
	elif gcd([gcd1, a[n - 2], n - 1]) == 1:
		print(2)
	else:
		print(3)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	g = arr[0]
	for i in range(1, n):
		g = math.gcd(arr[i], g)
	if g == 1:
		print(0)
	elif n == 1:
		print(1)
	elif math.gcd(g, n) == 1:
		print(1)
	elif math.gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import gcd
t = int(input())
while t:
	n = int(input())
	nums = list(map(int, input().split()))
	d = nums[0]
	for i in range(1, len(nums)):
		d = gcd(d, nums[i])
	if d == 1:
		print('0')
	elif gcd(n, d) == 1:
		print('1')
	elif gcd(n - 1, d) == 1:
		print('2')
	else:
		print('3')
	t -= 1


from math import gcd

def codeforces(a):
	x = a[0]
	ind = 1
	n = len(a)
	for i in a:
		x = gcd(x, i)
	if x == 1:
		return 0
	for i in a:
		if gcd(ind, x) == 1:
			ans = ind
		ind += 1
	return min(n - ans + 1, 3)
t = int(input())
for test in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	print(codeforces(a))


T = int(input())
from math import gcd
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	total = a[0]
	for i in a:
		total = gcd(total, i)
	if total == 1:
		print(0)
		continue
	prev = total
	cost = 0
	for i in range(n - 1, -1, -1):
		if gcd(total, i + 1) == 1:
			cost = n - i
			break
		curr = gcd(prev, i + 1)
		if curr == 1:
			cost = cost + n - i
			break
		if curr < prev:
			cost = cost + n - i
		prev = curr
	print(cost)


from math import gcd
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if n == 1:
		if arr[0] == 1:
			print(0)
		else:
			print(1)
	else:
		t = arr[0]
		for i in range(1, n):
			t = gcd(t, arr[i])
		if t == 1:
			print(0)
		elif gcd(t, n) == 1:
			print(1)
		elif gcd(t, n - 1) == 1:
			print(2)
		else:
			print(3)


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	d = [*map(int, input().split())]
	g = d[0]
	for i in d:
		g = math.gcd(g, i)
	if g == 1:
		print(0)
		continue
	if math.gcd(g, n) == 1:
		print(1)
	elif math.gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	t = arr[0]
	for el in arr:
		t = gcd(t, el)
	if t == 1:
		print(0)
	elif gcd(t, n) == 1:
		print(1)
	elif gcd(t, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import *
t = int(input())
for i in range(t):
	n = int(input())
	lst = [int(x) for x in input().split()]
	gcd_arr = lst[0]
	for i in range(1, n):
		gcd_arr = gcd(gcd_arr, lst[i])
	if gcd_arr == 1:
		print(0)
		continue
	if n == 1:
		print(1)
		continue
	last_gcd = gcd(lst[n - 1], n)
	secondlast_gcd = gcd(lst[n - 2], n - 1)
	if gcd(last_gcd, gcd_arr) == 1:
		print(1)
		continue
	if gcd(secondlast_gcd, gcd_arr) == 1:
		print(2)
		continue
	print(3)


from math import gcd

def gcd_list(a):
	t = a[0]
	for x in a:
		t = gcd(t, x)
	return t

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if gcd_list(a) == 1:
		print(0)
	else:
		t = a[-1]
		a[-1] = gcd(a[-1], n)
		if gcd_list(a) == 1:
			print(1)
		else:
			a[-1] = t
			a[-2] = gcd(a[-2], n - 1)
			if gcd_list(a) == 1:
				print(2)
			else:
				print(3)
for _ in range(int(input())):
	solve()


import math

def solve(res):
	g = res[0]
	for i in range(1, len(res)):
		g = math.gcd(g, res[i])
	if g == 1:
		return 0
	elif math.gcd(g, len(res)) == 1:
		return 1
	elif math.gcd(g, len(res) - 1) == 1:
		return 2
	else:
		return 3
t = int(input())
for _ in range(t):
	n = int(input())
	res = list(map(int, input().split()))
	print(solve(res))


import math
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	g = 0
	for i in a:
		g = math.gcd(g, i)
	if g == 1:
		print(0)
	elif math.gcd(g, n) == 1:
		print(1)
	elif math.gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import *
_ = int(input())
for i in range(_):
	k = int(input())
	lst = list(map(int, input().split()))
	vgcd = lst[0]
	for j in range(len(lst)):
		vgcd = gcd(vgcd, lst[j])
	if vgcd == 1:
		print(0)
	elif gcd(vgcd, k) == 1:
		print(1)
	elif gcd(vgcd, k - 1) == 1:
		print(2)
	else:
		print(3)


from math import *
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = a[0]
	for val in a:
		t = gcd(val, t)
	if t == 1:
		print(0)
	else:
		c_t = t
		t = gcd(n, t)
		if t == 1:
			print(1)
		else:
			c_t = gcd(n - 1, c_t)
			if c_t == 1:
				print(2)
			else:
				print(3)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for i in range(1, n):
		g = math.gcd(g, a[i])
	if g == 1:
		print(0)
		continue
	g1 = math.gcd(g, n)
	if g1 == 1:
		print(1)
		continue
	g1 = math.gcd(g, n - 1)
	if g1 == 1:
		print(2)
		continue
	else:
		print(3)
		continue


import math

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	GCD = lst[0]
	for i in range(1, n):
		GCD = math.gcd(lst[i], GCD)
	if GCD == 1:
		print(0)
	elif math.gcd(n, lst[n - 1]) == 1 or math.gcd(GCD, math.gcd(n, lst[n - 1])) == 1:
		print(1)
	elif math.gcd(n - 1, lst[n - 2]) == 1 or math.gcd(GCD, math.gcd(n - 1, lst[n - 2])) == 1:
		print(2)
	else:
		print(3)
t = int(input())
while t:
	solve()
	t = t - 1


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		if a[0] == 1:
			print(0)
		else:
			print(1)
		continue
	res = gcd(a[0], a[1])
	for i in range(2, n):
		res = gcd(res, a[i])
	if res == 1:
		print(0)
	elif gcd(res, gcd(a[n - 1], n)) == 1:
		print(1)
	elif gcd(res, gcd(a[n - 2], n - 1)) == 1:
		print(2)
	else:
		print(3)


import math

def gcd_f(res):
	g = res[0]
	for i in range(1, len(res)):
		g = math.gcd(g, res[i])
	if g == 1:
		return 0
	elif math.gcd(g, len(res)) == 1:
		return 1
	elif math.gcd(g, len(res) - 1) == 1:
		return 2
	return 3
for _ in range(int(input())):
	n = int(input())
	a_arr = list(map(int, input().split()))
	print(gcd_f(res=a_arr))


import math
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	ans = A[0]
	for i in range(n):
		ans = math.gcd(ans, A[i])
	if ans == 1:
		print(0)
	elif math.gcd(ans, n) == 1:
		print(1)
	elif math.gcd(ans, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import gcd

def gcd_arr(arr):
	answer = arr[0]
	for i in arr[1:]:
		answer = gcd(answer, i)
	return answer
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	if gcd_arr(nums) == 1:
		print(0)
	elif gcd_arr(nums[:n - 1] + [gcd(nums[-1], n)]) == 1:
		print(1)
	elif gcd_arr(nums[:n - 2] + [gcd(nums[-2], n - 1)] + [nums[-1]]) == 1:
		print(2)
	else:
		print(3)


import math
import bisect
from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		ans = math.gcd(ans, i)
	if ans == 1:
		print(0)
	elif math.gcd(ans, n) == 1:
		print(1)
	elif math.gcd(ans, n - 1) == 1:
		print(2)
	else:
		print(3)


import sys, math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		c = math.gcd(a[i], c)
	if c == 1:
		print(0)
	elif n == 1 or math.gcd(n, c) == 1:
		print(1)
	elif math.gcd(n - 1, c) == 1:
		print(2)
	else:
		print(3)


from math import gcd
primes = [1, 2, 3, 5, 7, 11, 13, 17, 19]

def main():
	n = int(input())
	a = list(map(int, input().split()))
	g = a[0]
	for x in a[1:]:
		g = gcd(g, x)
	if g == 1:
		print(0)
		return
	if gcd(g, n) == 1:
		print(1)
		return
	if gcd(g, n - 1) == 1:
		print(2)
		return
	print(3)
for _ in range(int(input())):
	main()


from math import gcd
test = int(input())
for t in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	s = 0
	for i in A:
		s = gcd(s, i)
	if s == 1:
		print(0)
	elif gcd(s, n) == 1:
		print(1)
	elif gcd(s, n - 1) == 1:
		print(2)
	else:
		print(3)


import math
t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	x = arr[0]
	for i in range(1, n):
		x = math.gcd(x, arr[i])
	if x == 1:
		print(0)
	elif n == 1:
		print(1)
	else:
		k = arr[-1]
		arr[-1] = math.gcd(n, k)
		y = arr[0]
		for i in range(1, n):
			y = math.gcd(y, arr[i])
		if y == 1:
			print(1)
			return
		arr[-1] = k
		k = arr[-2]
		arr[-2] = math.gcd(n - 1, k)
		y = arr[0]
		for i in range(1, n):
			y = math.gcd(y, arr[i])
		if y == 1:
			print(2)
			return
		arr[-2] = k
		print(3)
while t:
	solve()
	t -= 1


import math
N = 100010
a = [0] * N
t = int(input())
for _ in range(t):
	n = int(input())
	a[1:n + 1] = list(map(int, input().split()))
	gcd = a[1]
	for i in range(1, n + 1):
		gcd = math.gcd(gcd, a[i])
	if gcd == 1:
		print(0)
	elif math.gcd(math.gcd(n, a[n]), gcd) == 1:
		print(1)
	elif math.gcd(math.gcd(n - 1, a[n - 1]), gcd) == 1:
		print(2)
	else:
		print(3)


def helper(arr):
	ans = 0
	import math

	def checker(arr):
		g = arr[-1]
		for i in range(len(arr) - 1, -1, -1):
			g = math.gcd(g, arr[i])
		return g
	res = checker(arr)
	if res == 1:
		return 0
	if len(arr) == 1:
		return 1
	t1 = math.gcd(arr[-1], len(arr))
	arr1 = arr[:]
	arr1[-1] = t1
	t2 = math.gcd(arr[-2], len(arr) - 1)
	arr2 = arr[:]
	arr2[-2] = t2
	if checker(arr1) == 1:
		return 1
	if checker(arr2) == 1:
		return 2
	else:
		return 3
for i in range(int(input())):
	n = int(input())
	print(helper(list(map(int, input().split()))))


def gcd(a: int, b: int):
	while a != 0 and b != 0:
		if a >= b:
			a = a % b
		else:
			b = b % a
	return a + b

def gcd_a(a: list):
	res = a[0]
	for i in range(1, len(a)):
		res = gcd(res, a[i])
	return res

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	g = gcd_a(a)
	if g == 1:
		print(0)
	elif gcd(g, n) == 1:
		print(1)
	elif gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)

def main():
	k = int(input())
	for _ in range(k):
		solve()
main()


from typing import *
from collections import *
from math import *
from functools import *
INF = 1061109567

def RI():
	return int(input())

def RAI():
	return [int(i) for i in input().split()]

def RAI_1():
	return [INF] + RAI()

def slove():
	n = RI()
	a = RAI()
	s = reduce(gcd, a)
	if s == 1:
		print(0)
		return
	if gcd(s, gcd(n, a[n - 1])) == 1:
		print(1)
		return
	if gcd(s, gcd(n - 1, a[n - 2])) == 1:
		print(2)
		return
	print(3)

def main():
	t = 1
	t = RI()
	for _ in range(t):
		slove()
main()


T = int(input())
for t in range(T):
	n = int(input())
	A = [int(i) for i in input().split()]
	from math import gcd
	g = A[0]
	for i in A:
		g = gcd(i, g)
	if g == 1:
		print(0)
		continue
	elif gcd(g, gcd(n, A[n - 1])) == 1:
		print(1)
	elif gcd(g, gcd(gcd(n, A[n - 1]), A[n - 2])) == 1:
		print(1)
	elif gcd(g, gcd(n - 1, A[n - 2])) == 1:
		print(2)
	elif gcd(g, gcd(gcd(n - 1, A[n - 2]), A[n - 1])) == 1:
		print(2)
	else:
		print(3)


from math import gcd
t = int(input(''))
for j in range(t):
	n = int(input(''))
	l = list(map(int, input('').split()))
	g = l[0]
	if n == 1:
		if l[0] == 1:
			print(0)
		else:
			print(1)
		continue
	if n == 2:
		if gcd(l[0], l[1]) == 1:
			print(0)
			continue
		a = gcd(l[1], 2)
		if gcd(g, a) == 1:
			print(1)
		else:
			print(2)
		continue
	for i in range(0, n - 1):
		g = gcd(g, l[i + 1])
	c = 0
	e = 0
	if g == 1:
		print(0)
		continue
	for i in range(n - 1, n - 4, -1):
		a = gcd(l[i], i + 1)
		if gcd(a, g) == 1:
			print(n - i)
			e = 1
			break
	if e == 0:
		print(3)


import math
T = int(input())
for aa in range(T):
	input()
	ques = list(map(int, input().split()))
	if ques == [1]:
		print(0)
		continue
	if len(ques) == 1:
		print(1)
		continue
	all_gcd = math.gcd(ques[0], ques[1])
	for i in range(2, len(ques)):
		all_gcd = math.gcd(all_gcd, ques[i])
		if all_gcd == 1:
			break
	if all_gcd == 1:
		print(0)
		continue
	gcd_ai = math.gcd(ques[-1], len(ques))
	gcd_ai_1 = math.gcd(ques[-2], len(ques) - 1)
	if math.gcd(all_gcd, gcd_ai) == 1:
		print(1)
		continue
	if math.gcd(all_gcd, gcd_ai_1) == 1:
		print(2)
		continue
	print(3)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	if n == 1:
		if l[0] == 1:
			print(0)
		else:
			print(1)
		continue
	g = gcd(l[0], l[1])
	for i in range(2, len(l)):
		g = gcd(g, l[i])
	if g == 1:
		print(0)
	elif gcd(g, n) == 1:
		print(1)
	elif gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)


import math

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		g = arr[0]
		for i in range(n):
			g = math.gcd(g, arr[i])
		print(str(get_answ(g, n)))

def get_answ(g, n):
	rez = 0
	if g == 1:
		return rez
	elif math.gcd(g, n) == 1:
		rez = 1
	elif math.gcd(g, n - 1) == 1:
		rez = 2
	else:
		rez = 3
	return rez
main()


def find_gcd(my_list):
	result = my_list[0]
	for x in my_list[1:]:
		if result < x:
			temp = result
			result = x
			x = temp
		while x != 0:
			temp = x
			x = result % x
			result = temp
	return result
num_tests = int(input())
for _ in range(num_tests):
	L = int(input())
	arr = list(map(int, input().split()))
	cost = 0
	gcd = find_gcd(arr)
	if gcd == 1:
		print('0')
	elif find_gcd([find_gcd([arr[-1], L]), gcd]) == 1:
		print('1')
	elif find_gcd([find_gcd([arr[-2], L - 1]), gcd]) == 1:
		print('2')
	else:
		print('3')


import math

def gcd(arr):
	ans = arr[0]
	for i in arr:
		ans = math.gcd(ans, i)
	return ans

def fun(arr, n):
	if gcd(arr) == 1:
		return 0
	temp = arr[-1]
	arr[-1] = math.gcd(arr[-1], n)
	if gcd(arr) == 1:
		return 1
	arr[-1] = temp
	arr[-2] = math.gcd(arr[-2], n - 1)
	if gcd(arr) == 1:
		return 2
	else:
		return 3
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	print(fun(arr, n))
	t = t - 1


import math
T = int(input())
for tc in range(T):
	n = int(input())
	l1 = list(map(int, input().split()))
	ans = l1[0]
	for i in range(1, len(l1)):
		ans = math.gcd(ans, l1[i])
	if ans == 1:
		print(0)
	elif math.gcd(ans, n) == 1:
		print(1)
	elif math.gcd(ans, n - 1) == 1:
		print(2)
	else:
		print(3)


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

def find_gcd_arr(arr, lenarr):
	result = arr[0]
	for x in range(lenarr):
		result = find_gcd(result, arr[x])
	return result
t = int(input())
for x in range(t):
	arrLen = int(input())
	arr = list(map(int, input().split()))
	gcdArr = find_gcd_arr(arr, arrLen)
	if gcdArr == 1:
		print(0)
	elif find_gcd(gcdArr, arrLen) == 1:
		print(1)
	elif find_gcd(gcdArr, arrLen - 1) == 1:
		print(2)
	else:
		print(3)


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()))
	gcd = arr[0]
	for i in arr:
		gcd = find_gcd(gcd, i)
	if gcd == 1:
		print(0)
	elif find_gcd(gcd, n) == 1:
		print(1)
	elif find_gcd(gcd, n - 1) == 1:
		print(2)
	else:
		print(3)
	t -= 1


from math import gcd
import copy

def Gcd(L):
	a = L[0]
	n = len(L)
	for i in range(1, n):
		a = gcd(L[i], a)
	return a
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	if Gcd(L) == 1:
		print(0)
	elif gcd(Gcd(L), n) == 1:
		print(1)
	elif gcd(Gcd(L), n - 1) == 1:
		print(2)
	else:
		print(3)


t = int(input())

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

def isPrime(n):
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	v = arr[0]
	for el in arr:
		v = gcd(v, el)
	if v == 1:
		print(0)
	else:
		res = None
		for i in range(n, 0, -1):
			if gcd(v, i) == 1:
				res = n - i + 1
				break
		print(min(res, 3))


from math import gcd

def gcdArray(arr, idx=0):
	if idx == len(arr) - 1:
		return arr[idx]
	a = arr[idx]
	b = gcdArray(arr, idx + 1)
	return gcd(a, b)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		(*a,) = map(int, input().split())
		g = gcdArray(a)
		if g == 1:
			print(0)
		elif gcdArray([g, n]) == 1:
			print(1)
		elif gcdArray([g, n - 1]) == 1:
			print(2)
		else:
			print(3)
main()


def ii(a=False):
	i = input().split()
	try:
		if len(i) == 1 and (not a):
			return int(i[0])
		return list(map(int, i))
	except Exception:
		if len(i) == 1 and (not a):
			return i[0]
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii()):
	n = ii()
	a = ii(True)
	g = a[0]
	for i in a:
		g = gcd(g, i)
	if g == 1:
		print(0)
	elif gcd(g, n) == 1:
		print(1)
	elif gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)
	pass


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)

def solve(a):
	if len(a) == 1 and a[0] == 1:
		return 0
	gcd_ = a[0]
	for i in range(1, len(a)):
		if a[i] == 1:
			return 0
		gcd_ = gcd(gcd_, a[i])
	if gcd_ == 1:
		return 0
	gcd_acum = gcd_
	cost_acum = 0
	for i in range(len(a) - 1, -1, -1):
		gcd_ai = gcd(a[i], i + 1)
		cur_cost = len(a) - i
		if gcd_ai == 1:
			return cur_cost
		if gcd(gcd_, gcd_ai) == 1:
			return cur_cost
		gcd_acum = gcd(gcd_acum, gcd_ai)
		cost_acum += cur_cost
		if gcd_acum == 1:
			return cost_acum
t = int(input())
for _ in range(t):
	n = input()
	a = [int(e) for e in input().split()]
	print(solve(a))


import math

def gcd(x, y):
	if x == 0:
		return y
	else:
		return gcd(y % x, x)
for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	lst = num.copy()
	d = 0
	for i in range(n):
		d = gcd(d, num[i])
	if d == 1:
		print(0)
	elif gcd(d, n) == 1:
		print(1)
	elif gcd(d, n - 1) == 1:
		print(2)
	else:
		print(3)


from math import *
for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	c = l[0]
	for i in range(x):
		c = gcd(c, l[i])
	if c == 1:
		print(0)
	else:
		c = l[0]
		m = l[-1]
		l[-1] = gcd(x, l[-1])
		for i in range(x):
			c = gcd(c, l[i])
		if c == 1:
			print(1)
		else:
			c = l[0]
			l[-1] = m
			l[-2] = gcd(x - 1, l[-2])
			for i in range(x):
				c = gcd(c, l[i])
			if c == 1:
				print(2)
			else:
				print(3)


def find_hcf(a, b):
	while a != 0:
		temp = b % a
		b = a
		a = temp
	return b
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	if n == 1:
		if arr[0] == 1:
			print(0)
		else:
			print(1)
		continue
	hcf = find_hcf(arr[0], arr[1])
	for j in range(2, n):
		hcf = find_hcf(hcf, arr[j])
	cost = 0
	n_hcf = find_hcf(n, arr[n - 1])
	n1_hcf = find_hcf(n - 1, arr[n - 2])
	if hcf == 1:
		cost = 0
	elif n_hcf == 1 or find_hcf(n_hcf, hcf) == 1:
		cost = 1
	elif n1_hcf == 1 or find_hcf(n1_hcf, hcf) == 1:
		cost = 2
	else:
		cost = 3
	print(cost)


from math import gcd

def check_gcd(a):
	gcd_max = a[0]
	for elem in a:
		gcd_max = gcd(gcd_max, elem)
	return gcd_max
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1:
		if a[0] == 1:
			print(0)
		else:
			print(1)
		continue
	b = a[:]
	c = a[:]
	b[-1] = gcd(b[-1], n)
	c[-2] = gcd(c[-2], n - 1)
	if check_gcd(a) == 1:
		print(0)
	elif check_gcd(b) == 1:
		print(1)
	elif check_gcd(c) == 1:
		print(2)
	else:
		print(3)


import math
case = int(input())
for i in range(case):
	n = int(input())
	ll = list(map(int, input().split()))
	cost = 0
	g = ll[0]
	t = 0
	while t < n:
		g = math.gcd(g, ll[t])
		t += 1
	if g == 1:
		print(0)
	elif math.gcd(g, n) == 1:
		print(1)
	elif math.gcd(g, n - 1) == 1:
		print(2)
	else:
		print(3)


import math

def check_gcd(a):
	if len(a) == 1:
		return a[0]
	else:
		num1 = a[0]
		num2 = a[1]
		gcd = math.gcd(num1, num2)
		if len(a) > 2:
			for i in range(2, len(a)):
				gcd = math.gcd(gcd, a[i])
		return gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = 0
	t1 = 0
	t2 = 0
	while check_gcd(a) != 1:
		t += 1
		if t == 1:
			t1 = a[n - 1]
			a[n - 1] = math.gcd(a[n - 1], n)
		elif t == 2:
			a[n - 1] = t1
			t2 = a[n - 2]
			a[n - 2] = math.gcd(a[n - 2], n - 1)
		elif t == 3:
			a[n - 1] = math.gcd(a[n - 1], n)
	print(t)


def ucln(a, b):
	if b == 0:
		return a
	return ucln(b, a % b)
t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	gcd = a[0]
	for i in a:
		gcd = ucln(gcd, i)
	if gcd == 1:
		print(0)
	elif ucln(gcd, n) == 1:
		print(1)
	elif ucln(gcd, n - 1) == 1:
		print(2)
	else:
		print(3)
	t -= 1


import math

def func(arr, n):
	if n == 1:
		if arr[0] == 1:
			return 0
		else:
			return 1
	curr_gcd = 0
	for i in range(n - 2):
		curr_gcd = math.gcd(curr_gcd, arr[i])
	if math.gcd(math.gcd(curr_gcd, arr[-2]), arr[-1]) == 1:
		return 0
	if math.gcd(math.gcd(curr_gcd, arr[-2]), math.gcd(arr[-1], n)) == 1:
		return 1
	if math.gcd(math.gcd(curr_gcd, arr[-1]), math.gcd(arr[-2], n - 1)) == 1:
		return 2
	return 3
T = int(input())
for _ in range(T):
	n = int(input())
	arr = [int(x) for x in list(input().split(' '))]
	print(func(arr, n))


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

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	nod = a[0]
	for ai in a:
		nod = gcd(nod, ai)
	if nod == 1:
		print(0)
		return
	if n == 1 or gcd(nod, n) == 1:
		print(1)
	elif n > 1 and gcd(nod, n - 1) == 1:
		print(2)
	else:
		print(3)
t = int(input())
for _ in range(t):
	solve()


import math
for i in range(int(input())):
	k = int(input())
	li = list(map(int, input().split()))
	if len(li) == 1:
		if li[0] == 1:
			print(0)
		else:
			print(1)
		continue
	x = li[0]
	gc = math.gcd(li[0], li[1])
	f = 0
	for i in li[1:]:
		gc = math.gcd(gc, i)
		if gc == 1:
			print(0)
			f = 1
			break
	if f:
		continue
	temp = li
	temp2 = li.copy()
	temp[-1] = math.gcd(temp[-1], k)
	gc = math.gcd(temp[0], temp[1])
	x = temp[0]
	f = 0
	for i in temp[1:]:
		gc = math.gcd(gc, i)
		if gc == 1:
			print(1)
			f = 1
			break
	if f:
		continue
	temp2[-2] = math.gcd(temp2[-2], k - 1)
	gc = math.gcd(temp2[0], temp2[1])
	x = temp2[0]
	f = 0
	for i in temp2[1:]:
		gc = math.gcd(gc, i)
		if gc == 1:
			print(2)
			f = 1
			break
	if f:
		continue
	print(3)


import sys
import threading
from functools import lru_cache
from bisect import bisect_left
import math
from collections import defaultdict, deque
from heapq import *

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = [int(i) for i in input().split()]
		g = a[0]
		for index in range(1, n):
			g = math.gcd(a[index], g)
		if g == 1:
			print(0)
			continue
		ans = float('inf')
		for index in range(1, n + 1):
			if math.gcd(index, g) == 1:
				ans = min(ans, n - index + 1)
		for index in range(1, n):
			ans = min(ans, 2 * n - 2 * index + 1)
		print(ans)
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


def g(x, y):
	return g(y % x, x) if x else y
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(i) for i in input().split()]
	d = 0
	for i in range(n):
		d = g(d, a[i])
	if d == 1:
		print('0')
	elif g(d, n) == 1:
		print('1')
	elif g(d, n - 1) == 1:
		print('2')
	else:
		print('3')


from math import gcd

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

def il():
	return list(map(int, input().split()))
t = ii()
for q in range(t):
	n = ii()
	a = il()
	g = a[0]
	for i in range(1, n):
		g = gcd(min(g, a[i]), max(g, a[i]))
	print(0 if g == 1 else 1 if gcd(g, n) == 1 else 2 if gcd(g, n - 1) == 1 else 3)


def gcd(a, b):
	while a != 0 and b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		nod = l[0]
	else:
		a = l[0]
		b = l[1]
		nod = gcd(a, b)
		for x in range(2, n):
			a = nod
			b = l[x]
			nod = gcd(a, b)
	if nod == 1:
		print(0)
		continue
	elif gcd(nod, n) == 1:
		print(1)
	elif gcd(nod, n - 1) == 1:
		print(2)
	else:
		print(3)