Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are the owner of a big company. You are so rich, that the government has allowed you to print as many notes as you want of any single value that you like. You also have peculiar behavioral traits and you often do things that look weird to a third person. 

You have N employees, where the i-th employee has salary A_{i}. You want to pay them using a denomination that you create. You are also eco-friendly and wish to save paper. So, you wish to pay them using as few notes as possible. Find out the minimum number of notes required if you can alter the salary of at most one employee to any positive integer that you like, and choose the positive integer value that each note is worth (called its denomination).

Each employee must receive the exact value of his/her salary and no more.

------  Subtasks ------
Subtask #1 (100 points): Original constraints

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

- The first line contains an integer T, the number of test cases. Then the test cases follow.
- The first line of each test case contains a single integer N.
- The second line contains N integers A_{1}, A_{2}, \ldots, A_{N}, where A_{i} is the salary of the i-th employee.

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

For each test case, output in a single line the answer to the problem.

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

$1 ≤ T ≤ 12\cdot 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases is at most $10^{6}$.

----- Sample Input 1 ------ 
3
3
1 2 3
3
8 4 2
2
2 2 

----- Sample Output 1 ------ 
4
4
2

----- explanation 1 ------ 
Test Case $1$: We can change the salary of the third person to $1$ and use $1$ as the denomination. So in total we need $\frac{1}{1} + \frac{2}{1} + \frac{1}{1}$ = $1 + 2 + 1$ = $4$ notes.

Test Case $2$: We can change the salary of the first person to $2$ and use $2$ as the denomination. So in total we need $1 + 2 + 1$ = $4$ notes.

Test Case $3$: We can use $2$ as the denomination and we need not change the salary of any person. So in total we need $1 + 1$ = $2$ notes.

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
for z in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1 or n == 2:
		print(n)
		continue

	def gcd(x, y):
		while y:
			(x, y) = (y, x % y)
		return x
	g = a[0]
	p = [0] * n
	s = [0] * n
	s[n - 1] = 1
	p[0] = 1
	for i in range(1, n):
		p[i] = g
		g = gcd(g, a[i])
	g = a[n - 1]
	for i in range(n - 2, -1, -1):
		s[i] = g
		g = gcd(g, a[i])
	b = [0] * n
	b[0] = s[0]
	b[n - 1] = p[n - 1]
	for i in range(1, n - 1):
		b[i] = gcd(p[i], s[i])
	s = sum(a)
	m = (s - a[0] + b[0]) // b[0]
	for i in range(1, n):
		m = min(m, (s - a[i] + b[i]) // b[i])
	print(m)


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

def si():
	return input().split()

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

def ip():
	return input()
from math import gcd
for tastcas in range(int(input())):
	n = ii()
	a = li()
	m = s = sum(a)
	g = 0
	b = [0] * (n + 1)
	b[n - 1] = a[-1]
	if n < 3:
		print(n)
		continue
	for i in range(n - 2, -1, -1):
		b[i] = gcd(a[i], b[i + 1])
	for i in range(n):
		y = gcd(g, b[i + 1])
		y = (s - a[i] + y) // y
		g = gcd(g, a[i])
		if m > y:
			m = y
	print(m)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
T = int(input())
for test in range(T):
	n = int(input())
	A = [int(x) for x in input().split()]
	if n == 1:
		print(1)
		continue
	s = 0
	G = []
	for i in range(n + 1):
		if i < n:
			s += A[i]
		G.append(0)
	G[n - 1] = A[-1]
	for i in range(n - 2, -1, -1):
		G[i] = gcd(A[i], G[i + 1])
	m = s
	g = 0
	for i in range(n):
		y = gcd(g, G[i + 1])
		y = (s - A[i] + y) // y
		g = gcd(g, A[i])
		if y < m:
			m = y
	print(m)


from sys import stdin, stdout
from heapq import heapify, heappush, heappop
import sys
from collections import Counter
from copy import deepcopy
import math
sys.setrecursionlimit(10 ** 5)

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

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = []
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans
a = [0] * 1000000
f = [0] * 1000000
b = [0] * 1000000

def mapinput():
	return map(int, stdin.readline().split())

def strinput():
	return stdin.readline().strip()

def listinput():
	return list(map(int, stdin.readline().split()))

def intinput():
	return int(stdin.readline().strip())
for test in range(intinput()):

	def solve():
		n = intinput()
		arr = listinput()
		s = o = 0
		arr.sort()
		for i in range(n):
			a[i + 1] = arr[i]
		f[1] = a[1]
		b[n] = a[n]
		i = n - 1
		while i > 0:
			b[i] = gcd(b[i + 1], a[i])
			i -= 1
		i = 2
		while i <= n:
			f[i] = gcd(f[i - 1], a[i])
			i += 1
		for i in range(1, n + 1):
			s += a[i]
		m = 99999999999999999999999
		i = 1
		while i <= n:
			o = (s - a[i] + gcd(f[i - 1], b[i + 1])) // gcd(f[i - 1], b[i + 1])
			m = min(o, m)
			i += 1
		return int(m)
	print(solve())


import math

def hcf(a, b):
	if a > b:
		(a, b) = (b, a)
	while b != 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('1')
		continue
	fwd = [1] * n
	bwd = [1] * n
	fwd[0] = a[0]
	bwd[-1] = a[-1]
	gcd = [0] * n
	for i in range(1, n):
		fwd[i] = hcf(fwd[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		bwd[i] = hcf(bwd[i + 1], a[i])
	gcd[0] = bwd[1]
	gcd[n - 1] = fwd[n - 2]
	for i in range(1, n - 1):
		gcd[i] = hcf(fwd[i - 1], bwd[i + 1])
	total = sum(a)
	ans = math.inf
	for i in range(n):
		x = (total - a[i]) // gcd[i] + 1
		ans = min(x, ans)
	print(ans)


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	elif a == b:
		return a
	while a > 0:
		(a, b) = (b % a, a)
	return b
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if n == 1:
		ans = 1
	elif n == 2:
		ans = 2
	else:
		total = sum(x)
		pref = [0] * n
		suf = [0] * n
		for i in range(1, n):
			pref[i] = gcd(pref[i - 1], x[i - 1])
			suf[n - i - 1] = gcd(suf[n - i], x[n - i])
		ans = (total - x[0]) // gcd(pref[0], suf[0])
		for i in range(1, n):
			temp = (total - x[i]) // gcd(pref[i], suf[i])
			if temp < ans:
				ans = temp
		ans += 1
	print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = [int(i) for i in input().split()]
	if n == 1:
		print(1)
		continue
	elif n == 2:
		print(2)
		continue
	prefix = [arr[0]]
	for i in range(1, n):
		prefix.append(gcd(arr[i], prefix[i - 1]))
	suffix = [0] * n
	suffix[-2] = arr[-1]
	i = n - 1
	s = sum(arr)
	ans = int(s / prefix[n - 1])
	while i >= 0:
		if i == n - 1:
			x = int((s - arr[i]) / prefix[i - 1]) + 1
		else:
			suffix[i] = gcd(arr[i + 1], suffix[i + 1])
		if i == 0:
			x = int((s - arr[i]) / suffix[i]) + 1
		else:
			k = gcd(prefix[i - 1], suffix[i])
			x = int((s - arr[i]) / k) + 1
		ans = min(ans, x)
		i -= 1
	print(ans)


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	ans = float('inf')
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	sumo = 0
	for i in l:
		sumo += i
	bwd = [l[-1]]
	fwd = [l[0]]
	for i in range(n - 2, -1, -1):
		bwd.append(gcd(bwd[-1], l[i]))
	bwd = bwd[::-1]
	for i in range(1, n):
		fwd.append(gcd(fwd[i - 1], l[i]))
	main_arr = [1] * n
	main_arr[0] = bwd[1]
	main_arr[n - 1] = fwd[-2]
	for i in range(1, n - 1):
		main_arr[i] = gcd(bwd[i + 1], fwd[i - 1])
	for i in range(n):
		tmp = (sumo - l[i] + main_arr[i]) // main_arr[i]
		ans = min(ans, tmp)
	print(ans)


from math import gcd
from functools import reduce
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print(1)
		continue
	left = [0] * n
	right = [0] * n
	left[0] = 0
	left[1] = a[0]
	right[n - 1] = 0
	right[n - 2] = a[n - 1]
	for i in range(2, n):
		left[i] = gcd(left[i - 1], a[i - 1])
	for i in range(n - 3, -1, -1):
		right[i] = gcd(right[i + 1], a[i + 1])
	mid = [0] * n
	mid[0] = right[0]
	mid[n - 1] = left[n - 1]
	for i in range(1, n - 1):
		mid[i] = gcd(left[i], right[i])
	sum1 = sum(a)
	minvalue = 10 ** 16 + 7
	for i in range(n):
		value = (sum1 - a[i] + mid[i]) // mid[i]
		if value < minvalue:
			minvalue = value
	print(minvalue)


from sys import stdin

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	arr = [int(x) for x in stdin.readline().split()]
	if n == 1:
		print(1)
	else:
		sum_arr = sum(arr)
		(leftGCD, rightGCD) = ([arr[0]], [arr[n - 1]])
		for i in range(1, n):
			leftGCD.append(find_gcd(leftGCD[i - 1], arr[i]))
		for i in range(n - 2, -1, -1):
			rightGCD.append(find_gcd(arr[i], rightGCD[n - i - 2]))
		rightGCD.reverse()
		final_ans = float('inf')
		for i in range(0, n):
			rem_gcd = -1
			if i == 0:
				rem_gcd = rightGCD[i + 1]
			elif i == n - 1:
				rem_gcd = leftGCD[i - 1]
			else:
				rem_gcd = find_gcd(rightGCD[i + 1], leftGCD[i - 1])
			tmp = (sum_arr - arr[i]) // rem_gcd + 1
			if final_ans > tmp:
				final_ans = tmp
		print(final_ans)
	t -= 1


try:
	import math
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = list(map(int, input().split()))
		A.sort()
		f = []
		f.append(A[0])
		for i in range(1, n):
			f.append(math.gcd(f[i - 1], A[i]))
		b = []
		b.append(A[n - 1])
		for i in range(1, n):
			b.append(math.gcd(b[i - 1], A[n - 1 - i]))
		if n == 1 or n == 2:
			print(n)
		else:
			ans = float('inf')
			summ = sum(A)
			for i in range(n):
				if i == 0:
					x = b[n - 2]
				elif i == n - 1:
					x = f[n - 2]
				else:
					x = math.gcd(f[i - 1], b[n - 2 - i])
				ans = int(min(ans, (summ - A[i] + x) / x))
			print(ans)
except Exception:
	pass


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		total = l[0]
		prefix_gcd = [l[0]]
		suffix_gcd = [l[-1]]
		for i in range(1, n):
			prefix_gcd.append(gcd(min(l[i], prefix_gcd[-1]), max(l[i], prefix_gcd[-1])))
			total += l[i]
		for i in range(n - 2, -1, -1):
			suffix_gcd.append(gcd(min(l[i], suffix_gcd[-1]), max(l[i], suffix_gcd[-1])))
		suffix_gcd = suffix_gcd[::-1]
		best = min((total - l[0]) // suffix_gcd[1] + 1, (total - l[-1]) // prefix_gcd[-2] + 1)
		for i in range(1, n - 1):
			div = gcd(min(prefix_gcd[i - 1], suffix_gcd[i + 1]), max(prefix_gcd[i - 1], suffix_gcd[i + 1]))
			check = (total - l[i]) // div + 1
			best = min(best, check)
		print(best)


t = int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
while t:
	n = int(input())
	nums = list(map(int, input().split()))
	if len(nums) <= 1:
		print(1)
	else:
		left = [nums[0]]
		for i in range(1, len(nums)):
			left.append(find_gcd(left[i - 1], nums[i]))
		right = [0] * n
		right[n - 1] = nums[n - 1]
		for i in range(n - 2, -1, -1):
			right[i] = find_gcd(right[i + 1], nums[i])
		total = sum(nums)
		denomination = float('inf')
		for i in range(n):
			if i == 0:
				no_of_notes = (total - nums[i] + right[i + 1]) // right[i + 1]
				denomination = min(denomination, no_of_notes)
			elif i == n - 1:
				no_of_notes = (total - nums[i] + left[i - 1]) // left[n - 2]
				denomination = min(denomination, no_of_notes)
			else:
				no_of_notes = (total - nums[i] + find_gcd(left[i - 1], right[i + 1])) // find_gcd(left[i - 1], right[i + 1])
				denomination = min(denomination, no_of_notes)
		print(denomination)
	t -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	arr = [0] * (n + 1)
	for i in range(n):
		arr[i + 1] = l[i]
	arr = sorted(arr)
	pre = [0] * (n + 1)
	suff = [0] * (n + 2)
	pre[1] = arr[1]
	suff[n] = arr[n]
	i = n - 1
	while i > 0:
		suff[i] = math.gcd(suff[i + 1], arr[i])
		i = i - 1
	i = 2
	while i <= n:
		pre[i] = math.gcd(pre[i - 1], arr[i])
		i = i + 1
	sumi = sum(arr)
	i = 1
	mini = math.inf
	while i <= n:
		new = (sumi - arr[i] + math.gcd(pre[i - 1], suff[i + 1])) // math.gcd(pre[i - 1], suff[i + 1])
		mini = min(new, mini)
		i = i + 1
	print(mini)


def gcd(a, b):
	if a == 0:
		return b
	elif b == 0:
		return a
	elif b > a:
		return gcd(b, a)
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(arr) == 1:
		print(1)
	else:
		leftgcd = [0] * n
		rightgcd = [0] * n
		midgcd = [0] * n
		temp = 0
		for (key, val) in enumerate(arr):
			leftgcd[key] = temp
			if temp == 0:
				temp = val
			else:
				temp = gcd(temp, val)
		temp = 0
		for i in range(n - 1, -1, -1):
			key = i
			val = arr[key]
			rightgcd[key] = temp
			if temp == 0:
				temp = val
			else:
				temp = gcd(temp, val)
		for i in range(n):
			if leftgcd[i] == 0:
				midgcd[i] = rightgcd[i]
			elif rightgcd[i] == 0:
				midgcd[i] = leftgcd[i]
			else:
				midgcd[i] = gcd(leftgcd[i], rightgcd[i])
		mx = [0, 0]
		for (key, val) in enumerate(midgcd):
			mx = max(mx, [val, arr[key]])
		for (key, val) in enumerate(midgcd):
			if val == mx[0] and arr[key] == mx[1]:
				temp = key
				tempval = val
		arr[temp] = tempval
		sm = 0
		for item in arr:
			sm += item // tempval
		print(sm)


import math
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if len(a) == 1:
		print(1)
		continue
	prefix = [0 for i in range(n + 2)]
	suffix = [0 for i in range(n + 2)]
	prefix[1] = a[0]
	for i in range(2, n + 1):
		prefix[i] = math.gcd(prefix[i - 1], a[i - 1])
	suffix[n] = a[n - 1]
	for i in range(n - 1, 0, -1):
		suffix[i] = math.gcd(suffix[i + 1], a[i - 1])
	p = []
	ans = 0
	if prefix[n - 1] >= suffix[2]:
		p.append((sum(a[:n - 1]) + prefix[n - 1]) // prefix[n - 1])
		ans = prefix[n - 1]
	else:
		p.append((sum(a[1:]) + suffix[2]) // suffix[2])
		ans = suffix[2]
	for i in range(2, n):
		if math.gcd(prefix[i - 1], suffix[i + 1]) > ans:
			r = math.gcd(prefix[i - 1], suffix[i + 1])
			p.append((sum(a) - a[i - 1] + r) // r)
			ans = r
	print(p[-1])


import collections
from collections import defaultdict
import math
from math import gcd
from collections import Counter
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		print(1)
		continue
	left = [0] * n
	right = [0] * n
	(left[0], right[-1]) = (a[0], a[-1])
	for i in range(1, n):
		left[i] = gcd(a[i], left[i - 1])
	for i in range(n - 2, -1, -1):
		right[i] = gcd(a[i], right[i + 1])
	s = sum(a)
	ans = s // left[-1]
	ans = min(ans, (s - a[0] + right[1]) // right[1])
	ans = min(ans, (s - a[-1] + left[-2]) // left[-2])
	for i in range(1, n - 1):
		temp = gcd(left[i - 1], right[i + 1])
		newsum = s - a[i] + temp
		ans = min(ans, newsum // temp)
	print(ans)


def gcd(n, m):
	if n == 0:
		return m
	else:
		return gcd(m % n, n)
t = int(input())
for z in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		sum1 = sum(l)
		pre = [0] * n
		pre[0] = l[0]
		suf = [0] * n
		suf[-1] = l[-1]
		for i in range(1, n):
			pre[i] = gcd(pre[i - 1], l[i])
		for i in range(n - 2, -1, -1):
			suf[i] = gcd(suf[i + 1], l[i])
		ans = sum1 // pre[-1]
		for i in range(n):
			if i == 0:
				gcd1 = gcd(0, suf[i + 1])
			elif i == n - 1:
				gcd1 = gcd(pre[i - 1], 0)
			else:
				gcd1 = gcd(pre[i - 1], suf[i + 1])
			sum2 = sum1 - l[i]
			ans = min(ans, sum2 // gcd1 + 1)
		print(ans)


import math
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		sm = 0
		for i in arr:
			sm += i
		h = [0] * n
		f = [0] * n
		b = [0] * n
		f[0] = arr[0]
		for i in range(1, n):
			f[i] = math.gcd(f[i - 1], arr[i])
		b[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			b[i] = math.gcd(b[i + 1], arr[i])
		h[0] = b[1]
		h[n - 1] = f[n - 2]
		for i in range(1, n - 1):
			h[i] = math.gcd(f[i - 1], b[i + 1])
		mini = (sm - arr[0]) // h[0] + 1
		for i in range(1, n):
			curr = (sm - arr[i]) // h[i] + 1
			if curr < mini:
				mini = curr
		print(mini)


import math, sys
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	prefix = [0] * N
	suffix = [0] * N
	prefix[0] = arr[0]
	suffix[N - 1] = arr[N - 1]
	total = sum(arr)
	notes = sys.maxsize
	for i in range(1, N - 1):
		prefix[i] = math.gcd(arr[i], prefix[i - 1])
		suffix[N - 1 - i] = math.gcd(arr[N - i - 1], suffix[N - i])
	if N > 1:
		prefix[N - 1] = math.gcd(prefix[N - 2], arr[N - 1])
		suffix[0] = math.gcd(suffix[1], arr[0])
		for i in range(N):
			if i == 0:
				x = suffix[i + 1]
				rq = 1 + (total - arr[i]) / x
			elif i == N - 1:
				x = prefix[N - 2]
				rq = 1 + (total - arr[i]) / x
			else:
				x = math.gcd(prefix[i - 1], suffix[i + 1])
				rq = 1 + (total - arr[i]) / x
			if rq < notes:
				notes = rq
	else:
		notes = 1
	print(int(notes))


from math import ceil, gcd
inp = lambda x: map(int, x.split())
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(inp(input()))
	gcd_p = [[0, 0]]
	g = a[0]
	for i in range(n - 1):
		g = gcd(a[i], g)
		gcd_p.append([g, i + 1])
	g = a[n - 1]
	for i in range(n - 1, 0, -1):
		g = gcd(a[i], g)
		if gcd_p[i - 1][0] == 0:
			gcd_p[i - 1][0] = g
		else:
			gcd_p[i - 1][0] = gcd(gcd_p[i - 1][0], g)
	(m1, i1, n1) = (0, 0, 0)
	for i in range(n):
		if m1 == 0 or gcd_p[i][0] > m1 or (gcd_p[i][0] == m1 and a[gcd_p[i][1]] > n1):
			(m1, i1) = gcd_p[i]
			n1 = a[i1]
	cnt = 0
	for i in range(n):
		if i != i1:
			cnt += a[i] // m1
		else:
			cnt += 1
	print(cnt)


from collections import defaultdict
import sys, io, os
INP = sys.stdin.readline
inp = lambda : [*map(int, INP().encode().split())]
sinp = lambda : [*map(str, INP().split())]
out = sys.stdout.write

def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)
for _ in range(inp()[0]):
	n = inp()[0]
	d = defaultdict(int)
	l = inp()
	gcdpre = [l[0]]
	gcdsf = [l[-1]]
	total = l[0]
	for i in range(1, n):
		gcdpre.append(GCD(gcdpre[i - 1], l[i]))
		gcdsf.append(GCD(gcdsf[i - 1], l[n - 1 - i]))
		total += l[i]
	ans = total // gcdpre[-1]
	for i in range(n):
		t = 0
		if i != 0:
			t = gcdpre[i - 1]
		r = 0
		if i != n - 1:
			r = gcdsf[n - i - 2]
		x = GCD(t, r)
		if x != 0:
			ans = min(ans, (total - l[i]) // x + 1)
	print(ans)


import math
import itertools
from sys import stdin
from functools import reduce
from collections import deque
from sys import setrecursionlimit
from collections import defaultdict
input = stdin.readline

def I():
	return int(input())

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

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

def LIN(N):
	return [list(map(int, input().split())) for _ in range(N)]
gcd = math.gcd
Inf = float('Inf')

def solve():
	n = I()
	a = LI()
	total = sum(a)
	sum_ = [total - a[i] for i in range(n)]
	if n == 1:
		print(1)
	else:
		forward_gcd = [a[0]]
		for i in range(1, n):
			forward_gcd.append(gcd(forward_gcd[i - 1], a[i]))
		backward_gcd = [1 for i in range(n)]
		backward_gcd[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			backward_gcd[i] = gcd(backward_gcd[i + 1], a[i])
		gcd_ = [1 for i in range(n)]
		gcd_[0] = backward_gcd[1]
		gcd_[n - 1] = forward_gcd[n - 2]
		for i in range(1, n - 1):
			gcd_[i] = gcd(forward_gcd[i - 1], backward_gcd[i + 1])
		ans = Inf
		for i in range(n):
			ans = min(ans, sum_[i] // gcd_[i] + 1)
		print(ans)

def main():
	t = 1
	t = I()
	for i in range(1, t + 1):
		solve()
main()


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(arr) == 1:
		print(1)
		continue
	pre = [arr[0]]
	for i in range(1, n):
		pre.append(math.gcd(pre[i - 1], arr[i]))
	suf = [arr[-1]]
	for i in range(n - 2, -1, -1):
		suf.append(math.gcd(suf[-1], arr[i]))
	suf.reverse()
	total = sum(arr)
	ans = total // pre[-1]
	for i in range(n):
		ans = min(ans, (total - arr[i]) // math.gcd(0 if i - 1 < 0 else pre[i - 1], 0 if i + 1 >= n else suf[i + 1]) + 1)
	print(ans)


import math

def findgcd(l1, n):
	result = 0
	for i in range(n):
		result = math.gcd(l1[i], result)
		if result == 1:
			return 1
	return result
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst1 = []
	lst = sorted(lst)
	if n == 1:
		print(1)
	else:
		for k in range(n):
			lst1.append(0)
			m = lst[k]
			lst[k] = 0
			lst1[k] = findgcd(lst, n)
			lst[k] = m
		max1 = lst1[0]
		for j in range(n):
			if lst1[j] >= max1:
				max1 = lst1[j]
				m = j
		lst[m] = lst1[m]
		count = 0
		for j in range(n):
			count += lst[j] // max1
		print(count)


import random

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		total = sum(l)
		pr = []
		pr.append(l[0])
		for i in range(1, n):
			gcd = find_gcd(pr[i - 1], l[i])
			pr.append(gcd)
		ans = total // gcd
		pst = [0] * n
		pst[n - 1] = l[n - 1]
		for i in range(n - 2, -1, -1):
			gcd = find_gcd(pst[i + 1], l[i])
			pst[i] = gcd
		for i in range(n):
			if i - 1 < 0:
				k1 = 0
			else:
				k1 = pr[i - 1]
			if i + 1 > n - 1:
				k2 = 0
			else:
				k2 = pst[i + 1]
			k = find_gcd(k1, k2)
			ans = min(ans, (total - l[i]) // k + 1)
		print(ans)
	t -= 1


from collections import deque

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	no_change_gcd = 1
	if n == 1:
		print(1)
		continue
	pref_arr = deque()
	suff_arr = deque()
	pref_arr.append(arr[0])
	suff_arr.appendleft(arr[-1])
	for i in range(1, n):
		pref_arr.append(gcd(arr[i], pref_arr[-1]))
	for i in range(n - 2, -1, -1):
		suff_arr.appendleft(gcd(arr[i], suff_arr[0]))
	s = sum(arr)
	res = s // pref_arr[n - 1]
	for i in range(n):
		if i == 0:
			val = (s - arr[i]) // suff_arr[i + 1]
		elif i == n - 1:
			val = (s - arr[i]) // pref_arr[n - 2]
		else:
			val = (s - arr[i]) // gcd(pref_arr[i - 1], suff_arr[i + 1])
		res = min(res, val + 1)
	print(res)


import math
test = int(input())
for t in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	pre = [0, arr[0]]
	suff = [0] * (n + 1)
	total = arr[0]
	for i in range(1, n):
		total += arr[i]
		pre.append(math.gcd(pre[-1], arr[i]))
	for j in range(n - 1, -1, -1):
		suff[j] = math.gcd(suff[j + 1], arr[j])
	ans = float('inf')
	for i in range(n):
		x = math.gcd(pre[i], suff[i + 1])
		ans = min(ans, 1 + (total - arr[i]) // x)
	print(ans)


from math import gcd
t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().strip().split()))
	if n == 1:
		print(1)
		t -= 1
		continue
	prefix = [0] * n
	suffix = [0] * n
	prefix[0] = lst[0]
	suffix[n - 1] = lst[n - 1]
	for i in range(1, n):
		prefix[i] = gcd(prefix[i - 1], lst[i])
	for i in range(n - 2, -1, -1):
		suffix[i] = gcd(suffix[i + 1], lst[i])
	total = sum(lst)
	ans = total // prefix[n - 1]
	for i in range(n):
		a = lst[i]
		if i == 0:
			x = (total - a) // suffix[i + 1] + 1
		elif i == n - 1:
			x = (total - a) // prefix[i - 1] + 1
		else:
			x = (total - a) // gcd(prefix[i - 1], suffix[i + 1]) + 1
		ans = min(ans, x)
	print(ans)
	t -= 1


from math import gcd
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	a_sum = sum(lst)
	sum_ = [a_sum - lst[i] for i in range(n)]
	if n <= 2:
		print(n)
	else:
		(pref_lst, suf_lst, gcd_) = ([0] * n, [0] * n, [0] * n)
		(pref_lst[0], suf_lst[-1]) = (lst[0], lst[-1])
		for i in range(1, n):
			(pref_lst[i], suf_lst[-i - 1]) = (gcd(pref_lst[i - 1], lst[i]), gcd(suf_lst[-i], lst[-i - 1]))
		for i in range(n):
			(left_gcd, right_gcd) = (pref_lst[i - 1] if i > 0 else 0, suf_lst[i + 1] if i < n - 1 else 0)
			gcd_[i] = gcd(left_gcd, right_gcd)
		print(min([sum_[i] // gcd_[i] + 1 for i in range(n)]))


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	forward = [arr[0]]
	summe = arr[0]
	for i in range(1, n):
		val = gcd(arr[i], forward[i - 1])
		forward.append(val)
		summe += arr[i]
	backward = [1 for i in range(n)]
	backward[-1] = arr[-1]
	for i in range(n - 2, -1, -1):
		backward[i] = gcd(backward[i + 1], arr[i])
	gcd_all = [1 for _ in range(n)]
	gcd_all[0] = backward[1]
	gcd_all[-1] = forward[-2]
	for i in range(1, n - 1):
		gcd_all[i] = gcd(forward[i - 1], backward[i + 1])
	ans = float('inf')
	for i in range(n):
		val = (summe - arr[i]) // gcd_all[i] + 1
		ans = min(ans, val)
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total = sum(a)
	sum_ = [total - a[i] for i in range(n)]
	if n == 1:
		print(1)
	else:
		forward_gcd = [a[0]]
		for i in range(1, n):
			forward_gcd.append(gcd(forward_gcd[i - 1], a[i]))
		backward_gcd = [1 for i in range(n)]
		backward_gcd[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			backward_gcd[i] = gcd(backward_gcd[i + 1], a[i])
		gcd_ = [1 for i in range(n)]
		gcd_[0] = backward_gcd[1]
		gcd_[n - 1] = forward_gcd[n - 2]
		for i in range(1, n - 1):
			gcd_[i] = gcd(forward_gcd[i - 1], backward_gcd[i + 1])
		print(min([sum_[i] // gcd_[i] + 1 for i in range(n)]))


import math
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()][:n]
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		a.sort()
		(pre, suf, whole) = ([0] * n, [0] * n, [0] * n)
		(gcd_pre, gcd_suf) = (0, 0)
		(maxi, maxi_i) = (0, 0)
		for i in range(1, n - 1):
			gcd_pre = math.gcd(gcd_pre, a[i - 1])
			gcd_suf = math.gcd(gcd_suf, a[n - i])
			pre[i] = gcd_pre
			suf[n - 1 - i] = gcd_suf
		pre[n - 1] = math.gcd(a[n - 2], pre[n - 2])
		suf[0] = math.gcd(a[1], suf[1])
		for i in range(n):
			whole[i] = math.gcd(pre[i], suf[i])
			if whole[i] >= maxi:
				maxi = whole[i]
				maxi_i = i
		a[maxi_i] = maxi
		print(sum(a) // maxi)


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

def fGcd(arr):
	fHcf = []
	hcf = 0
	for i in arr:
		hcf = gcd(i, hcf)
		fHcf.append(hcf)
	return fHcf

def bGcd(arr):
	bHcf = []
	hcf = 0
	for i in range(len(arr) - 1, -1, -1):
		hcf = gcd(arr[i], hcf)
		bHcf.append(hcf)
	return bHcf[::-1]

def getHcf(fhcf, bhcf):
	hcf = []
	for i in range(len(fhcf)):
		if i == 0:
			hcf.append(bhcf[1])
		elif i == len(fhcf) - 1:
			hcf.append(fhcf[len(fhcf) - 2])
		else:
			hcf.append(gcd(fhcf[i - 1], bhcf[i + 1]))
	return hcf
for _ in range(int(input())):
	N = int(input())
	arr = [int(x) for x in input().split()]
	if N == 1:
		print(1)
	else:
		f = fGcd(arr)
		b = bGcd(arr)
		hcf = getHcf(f, b)
		s = sum(arr)
		ans = float('inf')
		for i in range(N):
			ans = min(ans, (s - arr[i]) // hcf[i] + 1)
		print(ans)


from math import gcd
from random import randint as rint
from sys import maxsize as mint
tn = int(input())
for _ in range(tn):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(n)
		continue
	arr.sort()
	sval = sum(arr)
	(fli, bli) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(n):
		fli[i + 1] = gcd(fli[i], arr[i])
		bli[n - i - 1] = gcd(bli[n - i], arr[n - i - 1])
	tval = mint
	for i in range(n):
		gd = gcd(fli[i], bli[i + 1])
		if (sval - arr[i]) % gd == 0:
			tval = min(tval, (sval - arr[i]) // gd + 1)
	print(tval)


from math import gcd as g
t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))[:n]
	if n == 1:
		print(1)
		t -= 1
		continue
	suffix = [0] * n
	prefix = [0] * n
	suffix[n - 1] = a[n - 1]
	prefix[0] = a[0]
	for i in range(1, n):
		prefix[i] = g(prefix[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		suffix[i] = g(suffix[i + 1], a[i])
	ans = []
	net = sum(a)
	for i in range(n):
		if i - 1 < 0:
			x = g(0, suffix[i + 1])
		elif i + 1 >= n:
			x = g(prefix[i - 1], 0)
		else:
			x = g(prefix[i - 1], suffix[i + 1])
		notes = (net - a[i]) // x + 1
		ans.append(notes)
	print(min(ans))
	t -= 1


from math import gcd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		prefix = [0] * n
		suffix = [0] * n
		(prefix[0], suffix[-1]) = (arr[0], arr[-1])
		for i in range(1, n):
			prefix[i] = gcd(arr[i], prefix[i - 1])
		for i in range(n - 2, -1, -1):
			suffix[i] = gcd(arr[i], suffix[i + 1])
		total = sum(arr)
		ans = total // prefix[-1]
		for i in range(n):
			s = total - arr[i]
			(a, b) = (0, 0)
			if i > 0:
				a = prefix[i - 1]
			if i < n - 1:
				b = suffix[i + 1]
			ans = min(ans, s // gcd(a, b) + 1)
		print(ans)


def simple_gcd(a, b):
	if b == 0:
		return a
	else:
		return simple_gcd(b, a % b)
T = int(input())
while T:
	N = int(input())
	A = list(map(int, input().split()))
	if N <= 2:
		print(N)
	else:
		P = [0 for x in range(N + 1)]
		S = [0 for x in range(N + 1)]
		for i in range(N):
			P[i + 1] = simple_gcd(P[i], A[i])
		for i in reversed(range(N)):
			S[i] = simple_gcd(S[i + 1], A[i])
		sum1 = sum(A)
		temp = float('inf')
		for i in range(N):
			gcd = simple_gcd(P[i], S[i + 1])
			temp = min(1 + (sum1 - A[i]) // gcd, temp)
		print(temp)
	T -= 1


import math
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	if n < 3:
		print(n)
	else:
		left = [a[0]]
		for i in range(1, n):
			temp = math.gcd(left[i - 1], a[i])
			left.append(temp)
		right = [0] * n
		right[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			temp = math.gcd(right[i + 1], a[i])
			right[i] = temp
		summ = sum(a)
		s = 1 + min(int((summ - a[0]) / right[1]), int((summ - a[n - 1]) / left[n - 2]))
		for i in range(1, n - 1):
			s = min(s, 1 + int((summ - a[i]) / math.gcd(right[i + 1], left[i - 1])))
		print(s)


import sys
import math
t = int(input())

def countAll(l, d):
	maxCoins = 0
	total = 0
	for i in l:
		coins = i // d
		if coins > maxCoins:
			maxCoins = coins
		total += coins
	total -= maxCoins
	total += 1
	return total
for _ in range(0, t):
	n = int(input())
	A = list(map(int, input().strip().split(' ')))
	if n == 1:
		print(1)
		continue
	l1 = []
	l2 = []
	s = 0
	g = A[0]
	g2 = A[-1]
	to = len(A)
	for i in range(0, to):
		g = math.gcd(g, A[i])
		g2 = math.gcd(g2, A[to - i - 1])
		l1.append(g)
		l2.append(g2)
		s += A[i]
	least = countAll(A, l1[-1])
	t_gcd = None
	for i in range(0, to):
		if i == 0:
			t_gcd = l2[to - 1 - 1]
		elif i == to - 1:
			t_gcd = l1[to - 1 - 1]
		else:
			t_gcd = math.gcd(l1[i - 1], l2[to - i - 2])
		t = (s - A[i]) // t_gcd + 1
		if t < least:
			least = t
	print(least)


import math
T = int(input())
for i in range(T):
	N = int(input())
	salary = [int(s) for s in input().split()]
	if N == 1:
		print(1)
	elif N == 2:
		print(2)
	else:
		salary.sort()
		gcd_left = [0] * N
		gcd_right = [0] * N
		gcd_l = 0
		gcd_r = 0
		for j in range(1, N - 1):
			gcd_l = math.gcd(gcd_l, salary[j - 1])
			gcd_r = math.gcd(gcd_r, salary[N - j])
			gcd_left[j] = gcd_l
			gcd_right[N - j - 1] = gcd_r
		gcd_left[N - 1] = math.gcd(salary[N - 2], gcd_left[N - 2])
		gcd_right[0] = math.gcd(salary[1], gcd_right[1])
		gcd_whole = [0] * N
		maxi = 0
		maxi_index = 0
		for j in range(N):
			gcd_whole[j] = math.gcd(gcd_left[j], gcd_right[j])
			if gcd_whole[j] >= maxi:
				maxi = gcd_whole[j]
				maxi_index = j
		salary[maxi_index] = maxi
		print(sum(salary) // maxi)


from math import gcd
j = []
j = [0] * 100
j.pop()
j.pop()
j.append(99)
j.pop()
j.sort()
j.append(1000)
j.sort()
for _ in range(int(input())):
	ans = float('inf')
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	sumo = 0
	for i in l:
		sumo += i
	bwd = [l[-1]]
	fwd = [l[0]]
	for i in range(n - 2, -1, -1):
		bwd.append(gcd(bwd[-1], l[i]))
	bwd = bwd[::-1]
	for i in range(1, n):
		fwd.append(gcd(fwd[i - 1], l[i]))
	main_arr = [1] * n
	main_arr[0] = bwd[1]
	main_arr[n - 1] = fwd[-2]
	for i in range(1, n - 1):
		main_arr[i] = gcd(bwd[i + 1], fwd[i - 1])
	for i in range(n):
		tmp = (sumo - l[i] + main_arr[i]) // main_arr[i]
		ans = min(ans, tmp)
	print(ans)


t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for test in range(0, t):
	n = int(input())
	a = input().split()
	a = list(map(int, a))
	gs = [0] * n
	gp = [0] * n
	g_exclude = [0] * n
	s = [0] * n
	ans = 0
	totsum = 0
	if n == 1:
		print(1)
		continue
	for i in a:
		totsum = totsum + i
	gp[0] = a[0]
	gs[n - 1] = a[n - 1]
	for i in range(1, n):
		gp[i] = gcd(gp[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		gs[i] = gcd(gs[i + 1], a[i])
	g_exclude[0] = gs[1]
	g_exclude[n - 1] = gp[n - 2]
	for i in range(1, n - 1):
		g_exclude[i] = gcd(gp[i - 1], gs[i + 1])
	for i in range(0, n):
		s[i] = int((totsum - a[i] + g_exclude[i]) / g_exclude[i])
	ans = s[0]
	for i in s:
		if i < ans:
			ans = i
	print(ans)


def gcd(num1, num2):
	if num2 == 0:
		return num1
	else:
		return gcd(num2, num1 % num2)

def MINNOTES():
	itrs = int(input())
	for itr in range(itrs):
		len_array = int(input())
		array = [int(i) for i in input().split()]
		if len_array == 1:
			print(1)
			continue
		gs = [0] * len_array
		gp = [0] * len_array
		g_exclude = [0] * len_array
		s = [0] * len_array
		total_sum = ans = 0
		for i in array:
			total_sum += i
		gp[0] = array[0]
		gs[len_array - 1] = array[len_array - 1]
		for i in range(1, len_array):
			gp[i] = gcd(gp[i - 1], array[i])
		for i in range(len_array - 2, -1, -1):
			gs[i] = gcd(gs[i + 1], array[i])
		g_exclude[0] = gs[1]
		g_exclude[len_array - 1] = gp[len_array - 2]
		for i in range(1, len_array - 1):
			g_exclude[i] = gcd(gp[i - 1], gs[i + 1])
		for i in range(0, len_array):
			s[i] = int((total_sum - array[i] + g_exclude[i]) // g_exclude[i])
		ans = s[0]
		for i in s:
			if i < ans:
				ans = i
		print(ans)
MINNOTES()


T = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for j in range(T):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n == 1:
		print(1)
		continue
	li1 = [0] * n
	li2 = [0] * n
	ghost = [0] * n
	s = [0] * n
	ans = 0
	totsum = 0
	for i in arr:
		totsum += i
	li2[0] = arr[0]
	li1[n - 1] = arr[n - 1]
	for i in range(1, n):
		li2[i] = gcd(li2[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		li1[i] = gcd(li1[i + 1], arr[i])
	ghost[0] = li1[1]
	ghost[n - 1] = li2[n - 2]
	for i in range(1, n - 1):
		ghost[i] = gcd(li2[i - 1], li1[i + 1])
	for i in range(0, n):
		s[i] = int((totsum - arr[i] + ghost[i]) / ghost[i])
	ans = s[0]
	for i in s:
		if i < ans:
			ans = i
	print(ans)


def gcd(c, d):
	if c == 0:
		return d
	elif d == 0:
		return c
	elif d > c:
		return gcd(d, c)
	else:
		return gcd(d, c % d)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(1)
	else:
		lgcd = [0] * n
		rgcd = [0] * n
		mgcd = [0] * n
		tp = 0
		for (key, val) in enumerate(l):
			lgcd[key] = tp
			if tp == 0:
				tp = val
			else:
				tp = gcd(tp, val)
		tp = 0
		for i in range(n - 1, -1, -1):
			key = i
			val = l[key]
			rgcd[key] = tp
			if tp == 0:
				tp = val
			else:
				tp = gcd(tp, val)
		for i in range(n):
			if lgcd[i] == 0:
				mgcd[i] = rgcd[i]
			elif rgcd[i] == 0:
				mgcd[i] = lgcd[i]
			else:
				mgcd[i] = gcd(lgcd[i], rgcd[i])
		mx = [0, 0]
		for (key, val) in enumerate(mgcd):
			mx = max(mx, [val, l[key]])
		for (key, val) in enumerate(mgcd):
			if val == mx[0] and l[key] == mx[1]:
				tp = key
				tpvl = val
		l[tp] = tpvl
		s = 0
		for it in l:
			s += it // tpvl
		print(s)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(arr) == 1:
		print(1)
	else:
		beforea = [0] * n
		aftera = [0] * n
		excepta = [0] * n
		temp = 0
		for i in range(len(arr)):
			beforea[i] = temp
			if temp == 0:
				temp = arr[i]
			else:
				temp = math.gcd(temp, arr[i])
		temp = 0
		for i in range(n - 1, -1, -1):
			key = i
			val = arr[key]
			aftera[key] = temp
			if temp == 0:
				temp = val
			else:
				temp = math.gcd(temp, val)
		for i in range(n):
			if beforea[i] == 0:
				excepta[i] = aftera[i]
			elif aftera[i] == 0:
				excepta[i] = beforea[i]
			else:
				excepta[i] = math.gcd(beforea[i], aftera[i])
		mx = [0, 0]
		for (key, val) in enumerate(excepta):
			mx = max(mx, [val, arr[key]])
		for (key, val) in enumerate(excepta):
			if val == mx[0] and arr[key] == mx[1]:
				temp = key
				tempval = val
		arr[temp] = tempval
		ans = 0
		for item in arr:
			ans += item // tempval
		print(ans)


T = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for j in range(T):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n == 1:
		print(1)
		continue
	gs = [0] * n
	gp = [0] * n
	g_exclude = [0] * n
	s = [0] * n
	ans = 0
	totsum = 0
	for i in arr:
		totsum += i
	gp[0] = arr[0]
	gs[n - 1] = arr[n - 1]
	for i in range(1, n):
		gp[i] = gcd(gp[i - 1], arr[i])
	for i in range(n - 2, -1, -1):
		gs[i] = gcd(gs[i + 1], arr[i])
	g_exclude[0] = gs[1]
	g_exclude[n - 1] = gp[n - 2]
	for i in range(1, n - 1):
		g_exclude[i] = gcd(gp[i - 1], gs[i + 1])
	for i in range(0, n):
		s[i] = int((totsum - arr[i] + g_exclude[i]) / g_exclude[i])
	ans = s[0]
	for i in s:
		if i < ans:
			ans = i
	print(ans)


from math import gcd
ll = int(input())

def make_back_forward(arr):
	forward = [0] * len(arr)
	back = [0] * len(arr)
	forward[0] = arr[0]
	back[-1] = arr[-1]
	for i in range(1, len(arr)):
		forward[i] = gcd(forward[i - 1], arr[i])
	for i in range(len(arr) - 2, -1, -1):
		back[i] = gcd(back[i + 1], arr[i])
	return (forward, back)
for ppp in range(ll):
	n = int(input())
	arr = list(map(int, input().split()))
	(forward, back) = make_back_forward(arr)
	summ = sum(arr)
	ans = float('inf')
	if n == 1:
		print(1)
		continue
	for i in range(1, len(arr) - 1):
		tmp = (summ - arr[i] + gcd(forward[i - 1], back[i + 1])) // gcd(forward[i - 1], back[i + 1])
		ans = min(ans, tmp)
	tmp = (summ - arr[0] + gcd(back[1], back[1])) // gcd(back[1], back[1])
	ans = min(ans, tmp)
	tmp = (summ - arr[n - 1] + gcd(forward[n - 2], forward[n - 2])) // gcd(forward[n - 2], forward[n - 2])
	ans = min(ans, tmp)
	print(ans)


t = int(input())

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

def gcd_missing(a):
	n = len(a)
	fgcd = [a[0]]
	rgcd = [a[n - 1]]
	gcd1 = a[0]
	gcd2 = a[n - 1]
	for i in range(1, n):
		gcd1 = gcd(gcd1, a[i])
		fgcd.append(gcd1)
	for j in range(n - 2, -1, -1):
		gcd2 = gcd(gcd2, a[j])
		rgcd.append(gcd2)
	gcd_m = []
	for k in range(n):
		if k == 0:
			gcd_m.append(rgcd[n - 2])
		elif k == n - 1:
			gcd_m.append(fgcd[n - 2])
		else:
			gcd_m.append(gcd(fgcd[k - 1], rgcd[n - k - 2]))
	return gcd_m
for _ in range(t):
	min_notes = []
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		gcd_m = gcd_missing(a)
		sa = sum(a)
		for i in range(n):
			min_notes.append((sa - a[i]) // gcd_m[i] + 1)
		print(min(min_notes))


import math
try:

	def solution(arr, n):
		if n == 1:
			return 1
		left = [0] * n
		right = [0] * n
		left[0] = 0
		left[1] = arr[0]
		right[n - 1] = 0
		right[n - 2] = arr[n - 1]
		for i in range(2, n):
			left[i] = math.gcd(left[i - 1], arr[i - 1])
		for i in range(n - 3, -1, -1):
			right[i] = math.gcd(right[i + 1], arr[i + 1])
		mid = [0] * n
		mid[0] = right[0]
		mid[n - 1] = left[n - 1]
		for i in range(1, n - 1):
			mid[i] = math.gcd(left[i], right[i])
		sm = sum(arr)
		value = 0
		minvalue = 10 ** 16 + 7
		for i in range(n):
			value = (sm - arr[i] + mid[i]) // mid[i]
			if value < minvalue:
				minvalue = value
		return minvalue
	for _ in range(int(input().strip())):
		n = int(input().strip())
		arr = list(map(int, input().strip().split()))
		print(solution(arr, n))
except:
	pass


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

def optimal_denomination1(arr):
	total = sum(arr)
	if len(arr) == 1:
		return 1
	f = [0 for _ in range(len(arr))]
	f[0] = arr[0]
	for i in range(1, len(arr)):
		f[i] = gcd(f[i - 1], arr[i])
	b = [0 for _ in range(len(arr))]
	b[-1] = arr[-1]
	for i in range(len(arr) - 2, -1, -1):
		b[i] = gcd(b[i + 1], arr[i])
	h = [0 for _ in range(0, len(arr))]
	h[0] = b[1]
	h[-1] = f[-2]
	for i in range(1, len(arr) - 1):
		h[i] = gcd(f[i - 1], b[i + 1])
	ans = float('inf')
	for i in range(0, len(arr)):
		s = (total - arr[i]) // h[i] + 1
		ans = min(ans, s)
	return ans
T = int(input())
while T:
	N = int(input())
	arr = list(map(int, input().split()))
	print(optimal_denomination1(arr))
	T -= 1


import math
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	su = sum(ar)
	f = [0] * n
	b = [0] * n
	h = [0] * n
	f[0] = ar[0]
	b[-1] = ar[-1]
	for i in range(1, n):
		f[i] = math.gcd(f[i - 1], ar[i])
	for i in range(n - 2, -1, -1):
		b[i] = math.gcd(b[i + 1], ar[i])
	(h[0], h[-1]) = (b[1], f[-2])
	for i in range(1, n - 1):
		h[i] = math.gcd(f[i - 1], b[i + 1])
	out = math.inf
	for i in range(n):
		s = (su - ar[i] + h[i]) // h[i]
		out = min(out, s)
	print(out)


t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(0, t):
	n = int(input())
	a = list(map(int, input('').strip().split()))[:n]
	if n == 1:
		print(1)
		continue
	g1 = [0] * n
	g2 = [0] * n
	ge = [0] * n
	g = [0] * n
	s = [0] * n
	ans = 0
	ts = 0
	for i in a:
		ts += i
	g2[0] = a[0]
	g1[n - 1] = a[n - 1]
	for i in range(1, n):
		g2[i] = gcd(g2[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		g1[i] = gcd(g1[i + 1], a[i])
	ge[0] = g1[1]
	ge[n - 1] = g2[n - 2]
	for i in range(1, n - 1):
		ge[i] = gcd(g2[i - 1], g1[i + 1])
	for i in range(0, n):
		s[i] = int((ts - a[i] + ge[i]) / ge[i])
	ans = s[0]
	for i in s:
		if i < ans:
			ans = i
	print(ans)


def hcfs(xray, yray):
	while yray:
		madebyritik = 1
		(xray, yray) = (yray, xray % yray)
	return xray
t = int(input())
while t:
	madebyritik = 1
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	(fi, bi, ri) = ([None] * n, [None] * n, [None] * n)
	madebyritik = 1
	reso = 0
	if len(arr) == 1:
		print(1)
	else:
		for y in range(n):
			madebyritik = 1
			fi[y] = hcfs(reso, arr[y])
			reso = fi[y]
		reso = 0
		for y in range(n - 1, -1, -1):
			madebyritik = 1
			bi[y] = hcfs(reso, arr[y])
			reso = bi[y]
		ri[0] = bi[1]
		ri[n - 1] = fi[n - 2]
		for y in range(1, n - 1):
			madebyritik = 1
			ri[y] = hcfs(bi[y + 1], fi[y - 1])
		if len(set(ri)) == 1:
			madebyritik = 1
			arr[-1] = ri[-1]
			reso = 0
			for value in arr:
				reso += value // arr[-1]
		else:
			madebyritik = 1
			maximum_hcf = arr[ri.index(max(ri))] = max(ri)
			reso = 0
			for value in arr:
				reso += value // maximum_hcf
		print(reso)
		madebyritik = 1
	t = t - 1


import math
t = int(input())
for test in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	GS = [0] * n
	GP = [0] * n
	G_EXCLUDE = [0] * n
	s = [0] * n
	ans = 0
	SUM = 0
	for i in a:
		SUM += i
	GP[0] = a[0]
	GS[n - 1] = a[n - 1]
	for i in range(1, n):
		GP[i] = math.gcd(GP[i - 1], a[i])
	for i in range(n - 2, -1, -1):
		GS[i] = math.gcd(GS[i + 1], a[i])
	G_EXCLUDE[0] = GS[1]
	G_EXCLUDE[n - 1] = GP[n - 2]
	for i in range(1, n - 1):
		G_EXCLUDE[i] = math.gcd(GP[i - 1], GS[i + 1])
	for i in range(0, n):
		s[i] = int((SUM - a[i] + G_EXCLUDE[i]) / G_EXCLUDE[i])
	ans = s[0]
	for i in s:
		if i < ans:
			ans = i
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print('1')
		continue
	gcdf = [1] * n
	gcdb = [1] * n
	h = [0] * n
	gcdf[0] = l[0]
	gcdb[n - 1] = l[n - 1]
	for i in range(1, n):
		gcdf[i] = math.gcd(gcdf[i - 1], l[i])
	for i in range(n - 2, -1, -1):
		gcdb[i] = math.gcd(gcdb[i + 1], l[i])
	h[0] = gcdb[1]
	h[n - 1] = gcdf[n - 2]
	for i in range(1, n - 1):
		h[i] = math.gcd(gcdf[i - 1], gcdb[i + 1])
	sum = 0
	for i in range(n):
		sum += l[i]
	ans = math.inf
	for i in range(n):
		s = (sum - l[i]) // h[i] + 1
		ans = min(s, ans)
	print(ans)