Master Shifu is training Po to become The Dragon Warrior and as a final assignment he must obtain maximum deliciousness from dumplings. There are  $N$ plates of dumplings in front of him with deliciousness $A_1, A_2, \ldots, A_N$, Po can choose any number of continuous plates of  dumplings. The total deliciousness is the sum of deliciousness of all the  chosen dumplings.
What is the minimum number of plates he must choose so that total deliciousness is maximum possible?
Note: Po must choose atleast one plate.

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output:-----
For each test case, print a single line containing one integer.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 2 \cdot 10^5$
- $0 \le A_i \le 10^9$

-----Sample Input:-----
2
4
1 2 3 4
5
3 2 0 3 0

-----Sample Output:-----
4
4

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
N = int(input())
for _ in range(N):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	count = 0
	last = 0
	for i in range(n):
		if arr[i] != 0:
			break
		last = i
		count += 1
	for i in arr[-1:last:-1]:
		if i != 0:
			break
		count += 1
	ans = n - count
	if ans == 0:
		print(1)
	else:
		print(ans)


for i in range(int(input())):
	n = int(input())
	a = [int(k) for k in input().split()]
	ind1 = 0
	ind2 = 0
	for j in range(len(a)):
		if a[j] == 0:
			continue
		else:
			ind1 = j
			break
	for k in range(len(a) - 1, -1, -1):
		if a[k] == 0:
			continue
		else:
			ind2 = k
			break
	print(len(a[ind1:ind2 + 1]))


tf = int(input())
for i in range(tf):
	np = int(input())
	nums = list(map(int, input().split()))
	s = sum(nums)
	if s == 0:
		print(1)
	else:
		l = 9999999
		sum1 = 0
		step = False
		ini = 0
		f = 0
		for i in range(np):
			sum1 += nums[i]
			while sum1 >= s and ini <= i:
				l = min(l, i - ini + 1)
				if l == 1:
					f = 1
					break
				sum1 -= nums[ini]
				ini += 1
				step = True
			if f == 1:
				break
			if step:
				sum1 -= nums[ini]
				ini += 1
		if f == 1:
			print(1)
		elif l != 9999999:
			print(l)
		else:
			print(1)


for _ in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	start = -1
	end = -1
	for i in range(0, n):
		if a[i] != 0:
			start = i
			break
	for i in range(len(a) - 1, -1, -1):
		if a[i] != 0:
			end = i
			break
	if start == end:
		print(1)
	else:
		print(end - start + 1)


try:
	n = int(input())
	for i in range(0, n):
		a = int(input())
		b = input().split()
		counta = 0
		countb = 0
		for j in range(a - 1, -1, -1):
			if b[j] == '0':
				countb = countb + 1
			else:
				break
		for k in range(0, a):
			if b[k] == '0':
				counta = counta + 1
			else:
				break
		count = counta + countb
		if count < a:
			print(a - count)
		else:
			print(1)
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split(' ')))
	start = 0
	while start < len(a) and a[start] == 0:
		start += 1
	end = n - 1
	while end >= 0 and a[end] == 0:
		end -= 1
	best = max(1, end - start + 1)
	print(best)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(l, r) = (0, n - 1)
	com = False
	while l <= r:
		if a[l] == 0:
			l += 1
		if a[r] == 0:
			r -= 1
		elif a[l] != 0 and a[r] != 0:
			print(r - l + 1)
			com = True
			break
	if not com:
		print(1)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	s = sum(li)
	if s == 0:
		print(1)
	else:
		m = n
		for i in range(n):
			if li[i] == 0:
				m -= 1
			else:
				break
		for i in range(n - 1, -1, -1):
			if li[i] == 0:
				m -= 1
			else:
				break
		print(m)


try:
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		total = sum(arr)
		if total == 0:
			print(1)
		else:
			start = 0
			while arr[start] == 0:
				start += 1
			x = 0
			count = 0
			for i in range(start, len(arr)):
				if x == total:
					break
				else:
					x += arr[i]
					count += 1
			print(count)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	while i < n and a[i] == 0:
		i += 1
	j = n - 1
	while a[j] == 0 and j > i:
		j -= 1
	print(j - i + 1 if j - i + 1 != 0 else 1)


import math

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	pos = n
	for i in range(n):
		if l[i] != 0:
			pos = i
			break
	c = 0
	for j in l[::-1]:
		if j == 0:
			c += 1
		else:
			break
	if n - c - pos > 0:
		print(n - c - pos)
	else:
		print(1)
t = input()
t = int(t)
while t != 0:
	t = t - 1
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	red = 0
	i = 0
	while red < n:
		if a[i] == 0:
			red += 1
		else:
			break
		i += 1
	i = n - 1
	while red < n:
		if a[i] == 0:
			red += 1
		else:
			break
		i -= 1
	if red < n:
		print(n - red)
	else:
		print('1')


t = int(input())
while t > 0:
	n = input()
	ls = input()
	ls = ls.split()
	st = ''
	for i in ls:
		if i == '0':
			st += ' '
		else:
			st += 'x'
	if len(st.strip()) == 0:
		print(1)
	else:
		print(len(st.strip()))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(ans1, ans2, f) = (0, 0, 21)
	for i in range(n):
		if a[i] != 0:
			ans1 = i
			f = 7
			break
	for j in range(n - 1, -1, -1):
		if a[j] != 0:
			ans2 = n - j - 1
			f = 7
			break
	if f != 7:
		print('1')
	else:
		print(n - (ans1 + ans2))


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	A = list(map(int, input().split()))
	sum1 = sum(A)
	cntzero = 0
	for i in range(N):
		if A[i] == 0:
			cntzero += 1
		else:
			break
	val = 0
	pos = 0
	for i in range(cntzero, N, 1):
		if val < sum1:
			val += A[i]
			pos += 1
		else:
			break
	if pos == 0:
		print('1')
	else:
		print(pos)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = 0
	iss = set()
	for i in range(n):
		if arr[i] == 0:
			x += 1
			iss.add(i)
		else:
			break
	for i in range(n - 1, -1, -1):
		if arr[i] == 0 and i not in iss:
			x += 1
		else:
			break
	print(max(1, n - x))


def count(lst):
	for i in range(0, len(lst)):
		if lst[-1] == 0:
			lst.pop()
		elif lst[0] == 0:
			lst.pop(0)
		else:
			break
	xx = lst.count(0)
	if xx == len(lst):
		print('1')
	else:
		print(len(lst))
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	count(lst)


for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	max_sum = sum(A)
	s = 0
	c = 0
	for i in range(n):
		if s == 0 and A[i] == 0:
			continue
		else:
			s += A[i]
			c += 1
			if s == max_sum:
				break
	if c == 0:
		print(1)
	else:
		print(c)


t = int(input())
for z in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	count = 0
	count2 = 0
	for i in L:
		if i == 0:
			count += 1
		else:
			break
	L.reverse()
	for j in L:
		if j == 0:
			count2 += 1
		else:
			break
	ans = n - count - count2
	if ans <= 0:
		ans = 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	suma = 0
	c = 0
	index1 = -1
	for i in range(n):
		if l[i] != 0:
			index1 = i
			break
	index2 = -1
	for i in range(n - 1, -1, -1):
		if l[i] != 0:
			index2 = i
			break
	if index1 != -1 and index2 != -1:
		print(index2 - index1 + 1)
	else:
		print(1)
	t -= 1


import numpy as np
t = int(input())
l = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	a = np.trim_zeros(a)
	if len(a) > 0:
		l.append(len(a))
	else:
		l.append(1)
for x in range(t):
	print(l[x])


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		if max(a) == 0:
			print(1)
		else:
			x = n
			for i in range(n):
				if a[i] == 0:
					x -= 1
				else:
					break
			for j in range(n - 1, -1, -1):
				if a[j] == 0:
					x -= 1
				else:
					break
			print(x)
except EOFError:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = -1
	x = 0
	y = 0
	while i < n:
		if a[i] != 0:
			x = i
			break
		else:
			i += 1
	while j > -n:
		if a[j] != 0:
			y = n + j
			break
		else:
			j -= 1
	print(y - x + 1)