You are given a sequence $a=[a_1,a_2,\dots,a_n]$ consisting of $n$ positive integers.

Let's call a group of consecutive elements a segment. Each segment is characterized by two indices: the index of its left end and the index of its right end. Denote by $a[l,r]$ a segment of the sequence $a$ with the left end in $l$ and the right end in $r$, i.e. $a[l,r]=[a_l, a_{l+1}, \dots, a_r]$.

For example, if $a=[31,4,15,92,6,5]$, then $a[2,5]=[4,15,92,6]$, $a[5,5]=[6]$, $a[1,6]=[31,4,15,92,6,5]$ are segments.

We split the given sequence $a$ into segments so that:

each element is in exactly one segment;

the sums of elements for all segments are equal.

For example, if $a$ = [$55,45,30,30,40,100$], then such a sequence can be split into three segments: $a[1,2]=[55,45]$, $a[3,5]=[30, 30, 40]$, $a[6,6]=[100]$. Each element belongs to exactly segment, the sum of the elements of each segment is $100$.

Let's define thickness of split as the length of the longest segment. For example, the thickness of the split from the example above is $3$.

Find the minimum thickness among all possible splits of the given sequence of $a$ into segments in the required way.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case is described by two lines.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the length of the sequence $a$.

The second line of each test case contains exactly $n$ integers: $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — elements of the sequence $a$.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2000$.


-----Output-----

For each test case, output one integer — the minimum possible thickness of a split of the sequence $a$ into segments.

Note that there always exist a split, you can always consider whole sequence as one segment.


-----Examples-----

Input
4
6
55 45 30 30 40 100
4
10 23 7 13
5
10 55 35 30 65
6
4 1 1 1 1 4
Output
3
4
2
3


-----Note-----

The split in the first test case is explained in the statement, it can be shown that it is optimal.

In the second test case, it is possible to split into segments only by leaving a single segment. Then the thickness of this split is equal to the length of the entire sequence, that is, $4$.

In the third test case, the optimal split will be $[10, 55], [35, 30], [65]$. The thickness of the split equals to $2$.

In the fourth test case possible splits are:

$[4] + [1, 1, 1, 1] + [4]$;

$[4, 1, 1] + [1, 1, 4]$.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Amortized analysis

Mathematics

Greedy algorithms


Solutions:
for s in [*open(0)][2::2]:
	d = {0: 0}
	t = i = 0
	for x in s.split():
		t += int(x)
		i += 1
		d[t] = i
	print(min((max((d.get(j, i) - d.get(j - x, -i) for j in range(x, t + 1, x))) for x in d if x and t % x < 1)))


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	sum_ = sum(arr)
	best = float('inf')
	for c in range(n, 0, -1):
		target = sum_ / c
		max_ = 0
		now = 0
		size = 0
		for x in arr:
			now += x
			size += 1
			if now > target:
				break
			if now == target:
				now = 0
				max_ = max(max_, size)
				size = 0
		else:
			if now == 0:
				max_ = max(max_, size)
				best = min(best, max_)
	out += str(best) + '\n'
print(out)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))

	def check(sm):
		maxi = 0
		cur = 0
		ln = 0
		for i in range(n):
			if cur > sm:
				return (False, -1)
			if cur < sm:
				cur += a[i]
				ln += 1
			else:
				maxi = max(maxi, ln)
				ln = 1
				cur = a[i]
		if cur == sm:
			return (True, max(maxi, ln))
		return (False, -1)
	t = sum(a)
	ans = n + 2
	for seg in range(1, n + 1):
		if t % seg:
			continue
		temp = check(t // seg)
		if temp[0]:
			ans = min(ans, temp[1])
	print(ans)


from genericpath import exists
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	p = [0]
	exists = {}
	for el in arr:
		p.append(p[-1] + el)
		exists[p[-1]] = len(p) - 1
	res = n
	for i in range(1, n + 1):
		if p[-1] % p[i] == 0:
			curr = i
			k = 1
			while p[i] * k < p[-1] and p[i] * (k + 1) in exists:
				curr = max(curr, exists[p[i] * (k + 1)] - exists[p[i] * k])
				k += 1
			if p[i] * k == p[-1]:
				res = min(res, curr)
	print(res)


def evaluate(A, target):
	ans = 0
	psum = 0
	count = 0
	for x in A:
		count += 1
		psum += x
		if psum == target:
			ans = max(ans, count)
			count = 0
			psum = 0
		elif psum > target:
			return -1
	return ans

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	candidates = []
	asum = sum(A)
	for i in range(n, 1, -1):
		if asum % i == 0:
			candidates.append(asum // i)
	ans = n
	for c in candidates:
		res = evaluate(A, c)
		if res != -1:
			ans = min(ans, res)
	return ans
for _ in range(int(input())):
	print(solve())


import sys
readline = sys.stdin.readline
T = int(readline())
for _ in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))
	ttl = sum(A)
	ans = N
	for i in range(2, N + 1):
		(q, r) = divmod(ttl, i)
		if r != 0:
			continue
		else:
			tmp = num = length = 0
			for a in A:
				tmp += a
				num += 1
				if tmp == q:
					tmp = 0
					length = max(length, num)
					num = 0
				elif tmp > q:
					break
			else:
				if tmp == 0:
					ans = min(ans, length)
	print(ans)


for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	s = sum(lst)
	lst1 = []
	for i in range(1, int(s ** (1 / 2)) + 1):
		if s % i == 0:
			if i <= n:
				lst1.append(i)
			if s // i <= n:
				lst1.append(s // i)
	lst1.append(s)
	lst1.sort(reverse=True)
	r_ans = 2000000
	for i in lst1:
		sm = s // i
		res = 0
		cnt = 0
		ans = 0
		for j in lst:
			cnt += 1
			ans = max(ans, cnt)
			res += j
			if res == sm:
				res = 0
				cnt = 0
			elif res > sm:
				break
		else:
			r_ans = min(r_ans, ans)
	print(r_ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	res = n
	for j in range(2, n + 1):
		if s % j == 0:
			d = s // j
			l = 0
			(x, y) = (0, 0)
			lst1 = []
			for i in range(n):
				d -= a[i]
				if d == 0:
					l = max(l, i - x + 1)
					x = i + 1
					d = s // j
				elif d < 0:
					l = n
					break
			else:
				res = min(l, res)
	print(res)


def Minimize_the_Thickness(n, A):
	divisor = []
	sum_v = sum(A)
	for i in range(n):
		if sum_v % (i + 1) == 0:
			divisor.append(sum_v / (i + 1))
	divisor.reverse()
	max_thick_all = float('inf')
	for j in divisor:
		k = 0
		sum_seg = 0
		thickness = 0
		max_thick = -float('inf')
		while k < n:
			sum_seg += A[k]
			thickness += 1
			if sum_seg == j:
				sum_seg = 0
				if thickness > max_thick:
					max_thick = thickness
				thickness = 0
			elif sum_seg > j:
				break
			k += 1
		if sum_seg == 0:
			if max_thick < max_thick_all:
				max_thick_all = max_thick
	return max_thick_all
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(Minimize_the_Thickness(n, a))


from bisect import bisect_left
from math import inf

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		(*nums,) = map(int, input().split())
		prefix = [0]
		for (i, value) in enumerate(nums):
			prefix.append(prefix[i] + value)
		ans = n
		for i in range(1, n + 1):
			num = prefix[i]
			multi = 2
			indexes = [i]
			trusted = False
			while num <= prefix[-1]:
				num = multi * prefix[i]
				index = bisect_left(prefix, num)
				if index <= n and prefix[index] == num:
					indexes.append(index)
					if index == n and prefix[index] == num:
						trusted = True
				else:
					break
				multi += 1
			thickness = -inf
			if trusted:
				for i in range(1, len(indexes)):
					thickness = max(thickness, indexes[i] - indexes[i - 1])
				thickness = max(indexes[0], thickness, 1)
				ans = min(ans, thickness)
		print(ans)
main()


def min_thickness(n, arr):
	divisor = []
	arr_sum = sum(arr)
	for i in range(n):
		if arr_sum % (i + 1) == 0:
			divisor.append(arr_sum / (i + 1))
	divisor.reverse()
	max_thick_all = float('inf')
	for j in divisor:
		i = 0
		(sum_seg, thick) = (0, 0)
		max_thick = float('-inf')
		while i < n:
			sum_seg += arr[i]
			thick += 1
			if sum_seg == j:
				sum_seg = 0
				max_thick = max(max_thick, thick)
				thick = 0
			elif sum_seg > j:
				break
			i += 1
		if sum_seg == 0:
			max_thick_all = min(max_thick_all, max_thick)
	return max_thick_all
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(min_thickness(n, arr))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ts = sum(arr)
	cs = 0
	minl = math.inf
	for i in range(n):
		cs += arr[i]
		maxl = i + 1
		if (ts - cs) % cs == 0:
			s = 0
			cl = 0
			for j in range(i + 1, n):
				s += arr[j]
				cl += 1
				if s == cs:
					s = 0
					maxl = max(maxl, cl)
					cl = 0
			if s == 0:
				minl = min(maxl, minl)
	print(minl)


for i in range(int(input())):
	n = int(input())
	mas = list(map(int, input().split()))
	sum_mas = sum(mas)
	min_ans = n
	for j in range(n, 0, -1):
		cur_ans = -1
		if sum_mas % j == 0:
			sum2 = sum_mas // j
			sum3 = 0
			h = False
			o = 0
			for z in range(n):
				if sum3 > sum2:
					h = True
					break
				elif sum3 == sum2:
					cur_ans = max(cur_ans, o)
					sum3 = 0
					o = 0
				sum3 += mas[z]
				o += 1
			if not h:
				if sum3 == sum2 or sum2 == 0:
					cur_ans = max(cur_ans, o)
					sum3 = 0
					o = 0
					min_ans = min(cur_ans, min_ans)
	print(min_ans)


import sys
input = sys.stdin.readline

def getMyDivisor(n):
	divisorsList = []
	for i in range(1, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			divisorsList.append(i)
			if i ** 2 != n:
				divisorsList.append(n // i)
	divisorsList.sort()
	return divisorsList
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	answer = n
	SUM = sum(a)
	for v in getMyDivisor(SUM):
		req = SUM / v
		flag = True
		s = 0
		length = 0
		MAX = 0
		for i in range(n):
			s += a[i]
			length += 1
			if s == req:
				MAX = max(length, MAX)
				s = 0
				length = 0
			elif s > req:
				flag = False
				break
		if flag:
			answer = min(answer, MAX)
	print(answer)


def check(values, size):
	max_thick = 0
	thick = 0
	sm = 0
	for v in values:
		thick += 1
		sm += v
		if sm > size:
			return -1
		if sm == size:
			max_thick = max(max_thick, thick)
			sm = 0
			thick = 0
	return max_thick

def thickness(n, values):
	mn_thick = n
	total = sum(values)
	factor = n
	while factor > 1:
		if total % factor == 0:
			size = total // factor
			thick = check(values, size)
			if thick != -1:
				mn_thick = min(mn_thick, thick)
		factor -= 1
	return mn_thick
for _ in range(int(input())):
	n = int(input())
	values = list(map(int, input().split()))
	print(thickness(n, values))


def check(arr, segment, totalsum):
	sumofone = totalsum // segment
	csum = 0
	clen = 0
	mxlen = -1
	segs = 0
	for val in arr:
		csum += val
		if csum < sumofone:
			clen += 1
		elif csum == sumofone:
			clen += 1
			mxlen = max(mxlen, clen)
			segs += 1
			csum = 0
			clen = 0
		else:
			csum = 0
			clen = 0
	if segs == segment:
		return mxlen
	return float('inf')
t = int(input())
while t > 0:
	n = int(input())
	ans = float('inf')
	a = list(map(int, input().split()))
	sumofarr = sum(a)
	for segments in range(1, n + 1):
		if sumofarr % segments == 0:
			ans = min(ans, check(a, segments, sumofarr))
	print(ans)
	t -= 1


for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split(' '))]
	s = sum(a)
	m = 0
	for p in range(1, n + 1):
		if p == 1:
			m = n
			continue
		d = s // p
		if d * p != s:
			continue
		r = 0
		t = 0
		b = True
		c = 0
		for i in range(n):
			r += a[i]
			c += 1
			if r > d:
				b = False
				break
			if r == d:
				t = max(t, c)
				r = 0
				c = 0
		else:
			m = min(m, t)
	print(m)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = n
	sum = 0
	s = 0
	for i in lis:
		s += i
	for i in range(n):
		sum += lis[i]
		ref = i + 1
		if s % sum == 0:
			cur_sum = 0
			lower = i + 1
			for j in range(i + 1, n):
				cur_sum += lis[j]
				if cur_sum == sum:
					cur_sum = 0
					ref = max(ref, j - lower + 1)
					lower = j + 1
			if cur_sum == 0:
				ans = min(ans, ref)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	di = dict()
	for i in range(1, n):
		lis[i] += lis[i - 1]
	for i in range(n):
		di[lis[i]] = i
	sum = lis[-1]
	ans = n
	for i in range(n):
		if sum % lis[i] == 0:
			cur_sum = lis[i] * 2
			last_ind = i + 1
			Mx = i + 1
			while cur_sum in di:
				Mx = max(Mx, di[cur_sum] - last_ind + 1)
				last_ind = di[cur_sum] + 1
				cur_sum += lis[i]
			if last_ind == n:
				ans = min(ans, Mx)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(sep=' ')))
	arr1 = []
	arr2 = []
	s = 0
	s1 = 0
	s2 = 0
	cnt = 0
	for j in range(n):
		s += arr[j]
	j = 0
	while j < n - 1:
		s1 += arr[j]
		if s % s1 == 0:
			arr1.append(s1)
		j = j + 1
	for k in range(len(arr1)):
		m = 0
		temp = m - 1
		s2 = 0
		for j in range(n):
			s2 += arr[j]
			if s2 == arr1[k]:
				s2 = 0
				if j - temp > m:
					m = j - temp
				temp = j
		if s2 == 0:
			arr2.append(m)
	if arr.count(arr[0]) == n:
		print(1)
	elif len(arr2) == 0 or (len(arr2) == 1 and arr2[0] == 1):
		print(n)
	else:
		print(min(arr2))


def check(arr, sum, l):
	count = 0
	Sum = 0
	diff = 0
	str = 0
	for i in range(len(arr)):
		Sum += arr[i]
		if Sum == sum:
			count += 1
			Sum = 0
			if i - str + 1 > diff:
				diff = i - str + 1
			str = i + 1
		elif Sum > sum:
			return 0
	if count == l:
		return diff
	return 0
a = int(input())
for i in range(a):
	b = int(input())
	array = list(map(int, input().split()))
	Sum = sum(array)
	min = len(array)
	for k in range(1, b + 1):
		if Sum / k == Sum // k and check(array, Sum / k, k) != 0:
			if min > check(array, Sum / k, k):
				min = check(array, Sum / k, k)
	print(min)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = []
	d = {}
	s = 0
	for i in range(n):
		s += a[i]
		d[s] = i
		p.append(s)
	x = n
	for i in range(n):
		o = i
		h = 2 * p[i]
		k = i + 1
		chk = 1
		while h <= s:
			if h in d:
				k = max(k, d[h] - o)
				o = d[h]
				h += p[i]
			else:
				chk = 0
				break
		if chk == 1 and h == s + p[i]:
			x = min(x, k)
	print(x)


def helper(n, a):
	sums = sum(a)
	temp = 0
	mini = n
	cnt = 0
	for i in range(n):
		temp += a[i]
		cnt += 1
		temp_max = 0
		if sums % temp == 0:
			temp_max = cnt
			(temp_sum, temp_cnt) = (0, 0)
			for j in range(i + 1, n):
				temp_sum += a[j]
				temp_cnt += 1
				if temp_sum == temp:
					temp_max = max(temp_max, temp_cnt)
					temp_sum = 0
					temp_cnt = 0
			if temp_sum == 0:
				mini = min(temp_max, mini)
	print(mini)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	helper(n, a)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = n
	di = dict()
	for i in range(1, n):
		lis[i] += lis[i - 1]
	for i in range(n):
		di[lis[i]] = i
	s = lis[-1]
	for i in range(n):
		if s % lis[i] == 0:
			mx = i + 1
			cnt = 1
			nxt_sum = lis[i] * 2
			while nxt_sum in di:
				mx = max(mx, di[nxt_sum] - di[nxt_sum - lis[i]])
				nxt_sum += lis[i]
				cnt += 1
			if cnt * lis[i] == s:
				ans = min(ans, mx)
	print(ans)


for s in [*open(0)][2::2]:
	d = {0: 0}
	t = i = 0
	j = 1
	m = 2000000000.0
	for x in s.split():
		t += int(x)
		i += 1
		d[t] = i
	for x in filter(None, d):
		try:
			if t % x < 1:
				m = min(m, max((d[i] - d[i - x] for i in range(x, t + 1, x))))
		except:
			x
	print(m)


for s in [*open(0)][2::2]:
	d = {0: 0}
	t = i = 0
	m = 2000000000.0
	for x in s.split():
		t += int(x)
		i += 1
		d[t] = i
	for x in d:
		try:
			if x and t % x < 1:
				m = min(m, max((d[i] - d[i - x] for i in range(x, t + 1, x))))
		except:
			x
	print(m)


for s in [*open(0)][2::2]:
	d = {0: 0}
	t = i = 0
	M = m = 2000000000.0
	for x in s.split():
		t += int(x)
		i += 1
		d[t] = i
	for x in d:
		if x and t % x < 1:
			m = min(m, max((d.get(i, M) - d.get(i - x, M) for i in range(x, t + 1, x))))
	print(m)


def fun(s, a):
	curr = 0
	l = 0
	ans = 0
	for i in range(len(a)):
		curr += a[i]
		l += 1
		if curr == s:
			ans = max(ans, l)
			l = 0
			curr = 0
		elif curr > s:
			return -1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	ans = -1
	tmp = 0
	for i in range(n):
		tmp += a[i]
		if s % tmp == 0:
			val = fun(tmp, a)
			if ans == -1 and val != -1:
				ans = val
			elif val != -1:
				ans = min(ans, val)
	if ans == -1:
		print(1)
	else:
		print(ans)


def cal(tong, ls, start, cand):
	if start >= len(ls):
		return len(ls)
	s = 0
	dem = 0
	for i in range(start, len(ls)):
		dem += 1
		s += ls[i]
		if s > tong:
			return
		if s == tong:
			s = 0
			cand.append(dem)
			dem = 0
	return max(cand)

def solve(ls):
	kq = float('inf')
	s = 0
	for j in range(len(ls)):
		s += ls[j]
	cur_s = 0
	for j in range(len(ls)):
		cur_s += ls[j]
		if s % cur_s == 0:
			m = cal(cur_s, ls, j + 1, [j + 1])
			if m != None and kq > m:
				kq = m
	return kq
l = []
n = int(input())
for i in range(n):
	k = int(input())
	ls = list(map(int, input().split()))
	l.append(solve(ls))
for i in l:
	print(i)


n = int(input())
for _ in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	s = sum(b)
	zx = 1000000
	for i in range(1, a + 1):
		if s % i:
			continue
		else:
			k = s / i
			s1 = 0
			lenzd = bz = syc = cd = 0
			for j in range(a):
				if s1 + b[j] > k:
					bz = 1
					break
				elif s1 + b[j] == k:
					s1 = 0
					cd = j - syc + 1
					syc = j + 1
					if cd > lenzd:
						lenzd = cd
				else:
					s1 += b[j]
			if bz:
				continue
			elif zx > lenzd:
				zx = lenzd
	print(zx)


import math

def minimize_the_thickness():
	n = int(input())
	a = [int(i) for i in input().split()]
	tot = 0
	for i in range(n):
		tot += a[i]
	ans = n
	for segs in range(1, n + 1):
		if tot % segs:
			continue
		req = tot / segs
		cur = 0
		at = 0
		possible = 1
		mx = 0
		for i in range(n):
			cur += a[i]
			if cur > req:
				possible = 0
			if cur == req:
				mx = max(i - at + 1, mx)
				at = i + 1
				cur = 0
		if possible:
			ans = min(ans, mx)
	print(ans)
for i in range(int(input())):
	minimize_the_thickness()


t = int(input())
res = list()
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	target = max(nums)
	p = [0] * n
	p[0] = nums[0]
	for i in range(1, n):
		p[i] = p[i - 1] + nums[i]
	ans = n
	for i in range(n):
		if p[i] < target:
			continue
		target = p[i]
		if p[n - 1] % target == 0:
			left = tmp = 0
			cnt = p[n - 1] // target
			x = 1
			for j in range(i, n):
				(div, mod) = divmod(p[j], target)
				if mod == 0 and div == x:
					tmp = max(tmp, j - left + 1)
					left = j + 1
					x += 1
			if x - 1 == cnt:
				ans = min(ans, tmp)
	res.append(ans)
for ans in res:
	print(ans)


for sminimizthick in [*open(0)][2::2]:
	d = {0: 0}
	tminimizthick = i = 0
	for x in sminimizthick.split():
		tminimizthick += int(x)
		i += 1
		d[tminimizthick] = i
	print(min((max((d.get(i, 99) - d.get(i - x, 0) for i in range(x, tminimizthick + 1, x))) for x in d if x and tminimizthick % x < 1)))


import math
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	for i in range(1, n, 1):
		a[i] = a[i - 1] + a[i]
	suma = a[n - 1]
	ans = 1000000000.0
	for i in range(1, n + 1, 1):
		if suma % i != 0:
			continue
		d = suma // i
		cnt = d
		last = -1
		maxv = 0
		for j in range(n):
			if a[j] == cnt:
				maxv = max(maxv, j - last)
				cnt += d
				last = j
		if cnt == suma + d:
			ans = min(ans, maxv)
	print(ans)


def getFactors(n):
	fac = [1]
	i = 2
	while i * i <= n:
		if n % i == 0:
			fac.append(i)
			if i * i != n:
				fac.append(n // i)
		i += 1
	fac.append(n)
	return fac
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	factors = getFactors(s)
	ans = 2 ** 31
	for f in factors:
		ess = s // f
		i = 0
		cs = 0
		cos = 0
		j = -1
		loes = 0
		while i < n:
			cs += arr[i]
			if cs == ess:
				cos += 1
				loes = max(loes, i - j)
				j = i
				cs = 0
			elif cs > ess:
				break
			i += 1
		if cs == ess:
			cos += 1
			loes = max(loes, i - 1 - j)
		if cos == f:
			ans = min(ans, loes)
	print(ans)


for a in [*open(0)][2::2]:
	d = {0: 0}
	t = i = 0
	for x in a.split():
		t += int(x)
		i += 1
		d[t] = i
	print(min((max((d.get(i, 99) - d.get(i - x, 0) for i in range(x, t + 1, x))) for x in d if x and t % x < 1)))


from math import log
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	b = []
	for i in range(n):
		v = s / (n - i)
		if v // 1 != v:
			continue
		t = 0
		c = True
		m = 0
		q = 0
		for j in range(n):
			t += a[j]
			q += 1
			if t > v:
				c = False
				break
			elif t == v:
				t = 0
				m = max(m, q)
				q = 0
		if c:
			b.append(m)
	print(min(b))


for _ in range(int(input())):
	n = int(input())
	wah = list(map(int, input().split(' ')))
	all_s = sum(wah)
	dels = []
	for i in range(1, int(all_s ** (1 / 2)) + 1):
		if all_s % i == 0:
			dels.append(i)
			num = all_s // i
			if num != i:
				dels.append(num)
	min_length = n
	for div in dels:
		s = 0
		flag = True
		max_length = 0
		need_sum = all_s // div
		start = 0
		for i in range(n):
			s += wah[i]
			if s > need_sum:
				flag = False
				break
			elif s == need_sum:
				s = 0
				max_length = max(max_length, i - start + 1)
				start = i + 1
		if start != n:
			flag = False
		if flag:
			min_length = min(max_length, min_length)
	print(min_length)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	pref = []
	s = 0
	d = {}
	for i in range(n):
		s += a[i]
		pref.append(s)
		d[s] = i
	ans = n
	for i in range(n - 1):
		if s % pref[i] != 0:
			continue
		k = s // pref[i]
		flag = True
		cur_ans = i + 1
		left_ind = i
		right_ind = i
		for j in range(2, k + 1):
			v = d.get(j * pref[i], -1)
			if v == -1:
				flag = False
				break
			right_ind = v
			cur_ans = max(cur_ans, right_ind - left_ind)
			left_ind = v
		if not flag:
			continue
		ans = min(ans, cur_ans)
	print(ans)


def exe():
	length = 0
	s = sum(lst)
	l = []
	while length <= n:
		length += 1
		sub_sum = s / length
		if sub_sum % 1 != 0:
			continue
		max_len = 0
		temp_sum = 0
		c = 0
		index = 0
		for i in range(n):
			temp_sum += lst[i]
			c += 1
			if temp_sum == sub_sum:
				max_len = max(c, max_len)
				c = 0
				temp_sum = 0
				index = i
		if max_len != 0 and index == n - 1:
			l.append(max_len)
	if len(l) == 0:
		return n
	else:
		return min(l)
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


def next_valid_index(a, start, goal):
	curr_sum = a[start]
	curr_index = start + 1
	while curr_sum < goal and curr_index < len(a):
		curr_sum += a[curr_index]
		curr_index += 1
	return curr_index if curr_sum == goal else -1

def max_width_by_sum(a, goal):
	curr_index = 0
	ans = 0
	while curr_index < len(a):
		next_index = next_valid_index(a, curr_index, goal)
		if next_index == -1:
			return len(a)
		ans = max(ans, next_index - curr_index)
		curr_index = next_index
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	summa = sum(a)
	left_sum = a[0]
	index = 1
	max_width = n
	while index < n:
		while summa % left_sum != 0 and index < n:
			left_sum += a[index]
			index += 1
		if summa % left_sum == 0:
			max_width = min(max_width, max_width_by_sum(a, left_sum))
			if index == n:
				break
			left_sum += a[index]
			index += 1
	print(max_width)


import math
T = int(input(''))
for i in range(T):
	n = int(input())
	str1 = input()
	l1 = [int(c) for c in str1.split()]
	total = 0
	for element in l1:
		total += element
	firstSum = 0
	j = 0
	max_dists = []
	index = 0
	while j < n:
		dist = []
		firstSum += l1[j]
		if total % firstSum == 0:
			dist.append(j + 1)
			index = j
			standard = firstSum
			k = j + 1
			secondSum = 0
			while k < n:
				secondSum += l1[k]
				if secondSum == standard:
					secondSum = 0
					dist.append(k - index)
					index = k
				k += 1
			if secondSum == 0:
				j += 1
				max_dists.append(max(dist))
				continue
			else:
				j += 1
		else:
			j += 1
	print(min(max_dists))


from bisect import bisect_left

def find_index(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	return -1

def solve():
	_ = int(input())
	v = [int(x) for x in input().split()]
	for i in range(1, len(v)):
		v[i] += v[i - 1]
	result = len(v)
	for s in v:
		if v[-1] % s != 0:
			continue
		max_segment = 0
		last_index = -1
		i = 1
		while i * s <= v[-1]:
			index = find_index(v, i * s)
			if index == -1:
				max_segment = 0
				break
			max_segment = max(max_segment, index - last_index)
			last_index = index
			i += 1
		if max_segment > 0:
			result = min(result, max_segment)
	print(result)
for _ in range(int(input())):
	solve()


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		s = sum(a)
		min_thickness = n
		for i in range(2, n + 1):
			if s % i == 0:
				val = s // i
				partition = True
				partial = 0
				found_thickness = 0
				thickness = 0
				for j in range(n):
					if partial > val:
						partition = False
						break
					if partial == val:
						partial = 0
						if thickness > found_thickness:
							found_thickness = thickness
						thickness = 0
					partial += a[j]
					thickness += 1
				if partial != val:
					partition = False
				if partial == val:
					partial = 0
					if thickness > found_thickness:
						found_thickness = thickness
					thickness = 0
				if partition and min_thickness > found_thickness:
					min_thickness = found_thickness
		print(min_thickness)
main()


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	total = sum(array)
	min_len = n
	for no_of_segments in range(1, n + 1):
		subarray_sum = total / no_of_segments
		if total % no_of_segments:
			continue
		(l, cur_len, cur_sum, segments) = (0, 0, 0, 0)
		for r in range(len(array)):
			cur_sum += array[r]
			if cur_sum == subarray_sum:
				segments += 1
				cur_len = max(cur_len, r - l + 1)
				l = r + 1
				cur_sum = 0
		if segments == no_of_segments:
			min_len = min(min_len, cur_len)
	print(min_len)


t = int(input())
while t > 0:
	n2 = int(input())
	arr = list(map(int, input().split()))
	sem = sum(arr)
	temp = 0
	cnt = 0
	result = n2
	for i in range(n2):
		temp = temp + arr[i]
		cnt += 1
		cnt1 = 0
		if sem % temp == 0:
			cnt1 = cnt
			t_s = 0
			t_c = 0
			for j in range(i + 1, n2):
				t_s = t_s + arr[j]
				t_c += 1
				if t_s == temp:
					cnt1 = max(t_c, cnt1)
					t_s = 0
					t_c = 0
			if t_s == 0:
				result = min(result, cnt1)
	print(result)
	t = t - 1


for s in [*open(0)][2::2]:
	d = {0: 0}
	k = i = 0
	for x in s.split():
		k += int(x)
		i += 1
		d[k] = i
	print(min((max((d.get(i, 99) - d.get(i - x, 0) for i in range(x, k + 1, x))) for x in d if x and k % x < 1)))


def cal(n, arr):
	if n == 1:
		return 1
	if len(set(arr)) == 1:
		return 1
	if n == 2:
		return 2
	t = [0] * n
	dic = {}
	for i in range(n):
		t[i] = arr[i] + t[i - 1]
		dic[t[i]] = i
	ans = n
	for i in range(n):
		if t[-1] % t[i] == 0:
			res = i + 1
			tag = t[i]
			st = i
			ck = 0
			for j in range(t[i] + tag, t[-1] + tag, tag):
				if j in dic:
					res = max(res, dic[j] - st)
					st = dic[j]
				else:
					ck = 1
					break
			if ck == 0:
				ans = min(ans, res)
	return ans
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(cal(n, arr))


import math
import collections

def func(k, n, psum, sum):
	i = 0
	temp = 0
	req = sum // k
	l1 = []
	while i < n:
		if psum[i] - temp == req:
			l1.append(i)
			temp = psum[i]
		i += 1
	if len(l1) == 0:
		return n
	if l1[-1] != n - 1:
		return n
	ans = l1[0] + 1
	for k in range(len(l1) - 1):
		ans = max(ans, l1[k + 1] - l1[k])
	return ans
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sum = 0
	for w in l:
		sum += w
	psum = []
	psum.append(l[0])
	for i in range(1, n):
		psum.append(l[i] + psum[-1])
	ans = n
	for j in range(1, n + 1):
		if sum % j != 0:
			continue
		else:
			ans = min(ans, func(j, n, psum, sum))
	print(ans)