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: interview

Starter code:

Solutions:
# cook your dish here
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(ind1,ind2)
    #print(a[ind1:ind2+1])
    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)

t=int(input())
for i in range(t):
    n=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(n):  
            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

# cook your dish here

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)

    # cook your dish here
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)


# cook your dish here
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()

# cook your dish here
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")


# cook your dish here
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

# cook your dish here
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
    #print(ans1,ans2)    
    if f!=7: print("1")
    else: print(n-(ans1+ans2))
    
                


# author dragonwarrior8 :D
# UMEED!! Lets make it yellow 5*
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])


# cook your dish here
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

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
    if lst.count(0)==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)

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)