Nikita just came up with a new array game. The rules are as follows:

Initially, Nikita has an array of integers.

In each move, Nikita must partition the array into $2$ non-empty contiguous parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets $1$ point; otherwise, the game ends.

After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array $\textbf{arr}$.

Nikita loves this game and wants your help getting the best score possible. Given $\textbf{arr}$, can you find and print the maximum number of points she can score?

For example, Nikita starts with the array $arr=[1,2,3,6]$.  She first splits it into $a1=[1,2,3]$ and $a2=[6]$, then discards $a2$.  $arr=a1\rightarrow a1=[1,2],a2=[3]$.  Discard $a2$ leaving $arr=[1,2]$.  This cannot be further split, so Nikita scored $2$.   

Function Description  

Complete the arraySplitting function in the editor below.  It should return an integer that reperesents the number of times Nikita can split the array.  

arraySplitting has the following parameter(s):  

arr: an array of integers  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ pairs of lines is as follows:  

The first line contains an integer $n$, the size of array $\textbf{arr}$.
The next line contains $n$ space-separated integers $arr\left[i\right]$.  

Constraints

$1\leq t\leq10$
$1\leq n\leq2^{14}$
$0\leq ar r[i]\leq10^9$

Scoring     

$1\leq n\leq2^8$ for $30\%$ of the test data
$1\leq n\leq2^{11}$ for $\textbf{60\%}$ of the test data
$1\leq n\leq2^{14}$ for $\textbf{100\%}$ of the test data

Output Format

For each test case, print Nikita's maximum possible score on a new line.

Sample Input
3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

Sample Output
0
2
3

Explanation

Test Case 0:  

Nikita cannot partition $\mbox{A}$ into $2$ parts having equal sums. Therefore, her maximum possible score is $0$ and we print $0$ on a new line.

Test Case 1:  

Initially, $\mbox{A}$ looks like this: 

She splits the array into $2$ partitions having equal sums, and then discards the left partition:   

She then splits the new array into $2$ partitions having equal sums, and then discards the left partition:      

At this point the array only has $1$ element and can no longer be partitioned, so the game ends. Because Nikita successfully split the array twice, she gets $2$ points and we print $2$ on a new line.

Test Case 2:

array		a1	a2
[4,1,0,1,1,0,1]	[4]	[1,0,1,1,0,1]
[1,0,1,1,0,1]	[1,0,1]	[1,0,1]
[1,0,1]		[1,0]	[1]

The answer is $3$.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import math

def solve(a):
	s = sum(a)
	if s % 2:
		return 0
	s //= 2
	t = 0
	for i in range(len(a)):
		t += a[i]
		if t == s:
			return 1 + max(solve(a[:i + 1]), solve(a[i + 1:]))
		if t > s:
			return 0

def solve0(n):
	return n - 1
t = int(input().strip())
for test in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	if sum(a) == 0:
		print(solve0(n))
	else:
		print(solve(a))


score = 0
score_inc = 1
tcs = int(input())

def score(arr):
	if sum(arr) % 2 != 0:
		return 0
	else:
		target = sum(arr) / 2
		for i in range(len(arr)):
			if sum(arr[0:i + 1]) == target:
				left = score(arr[0:i + 1])
				right = score(arr[i + 1:])
				if left >= right:
					return 1 + left
				else:
					return 1 + right
		return 0
for i in range(tcs):
	N = int(input())
	A = [int(num) for num in input().split(' ') if int(num) != 0]
	if A == []:
		print(N - 1)
	else:
		print(score(A))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	score = 0
	fsum = A
	h = {fsum[0]: 0}
	for i in range(1, N):
		fsum[i] += fsum[i - 1]
		h[fsum[i]] = i
	anchors = {0: True}
	if fsum[-1] == 0:
		score = N - 1
	elif fsum[-1] % 2 == 0:
		offset = fsum[-1] / 2
		while anchors:
			for a in list(anchors.keys()):
				if a + offset in h:
					anchors[a + offset] = True
				else:
					del anchors[a]
			if anchors:
				score += 1
			if offset % 2 == 0:
				offset /= 2
			else:
				anchors = None
	print(score)


t = int(input())
import sys
sys.setrecursionlimit(100000)

def partition(i, j, cuts):
	if i == j - 1:
		return cuts
	if i == 0:
		initial = 0
	else:
		initial = sumLEFT[i - 1]
	for k in range(i, j):
		if sumLEFT[k] - initial == sumLEFT[j - 1] - sumLEFT[k]:
			cuts += 1
			return max(partition(i, k + 1, cuts), partition(k + 1, j, cuts))
	return cuts
for _ in range(t):
	n = int(input())
	ar = [int(i) for i in input().split()]
	sumLEFT = [ar[0]]
	for i in range(1, n):
		sumLEFT.append(ar[i] + sumLEFT[i - 1])
	print(partition(0, n, 0))


import bisect

def b_in(a, x):
	i = bisect.bisect_left(a, x)
	return i < len(a) and a[i] == x
for _ in range(int(input())):
	input()
	arr = [int(x) for x in input().split()]
	cum_sum = [0]
	for n in arr:
		cum_sum.append(cum_sum[-1] + n)
	if cum_sum[-1] == 0:
		print(len(arr) - 1)
		continue
	best = 0
	q = [(cum_sum[0], cum_sum[-1], 0)]
	while q:
		(min_v, max_v, count) = q.pop()
		if count > best:
			best = count
		if (min_v + max_v) % 2 == 1:
			continue
		mid_v = (min_v + max_v) // 2
		if not b_in(cum_sum, mid_v):
			continue
		q.append((min_v, mid_v, count + 1))
		q.append((mid_v, max_v, count + 1))
	print(best)


def get_points(numbers, r_sum):
	l_sum = 0
	num_size = len(numbers)
	if num_size == 1:
		return 0
	if r_sum == 0:
		return num_size - 1
	for i in range(num_size):
		l_sum += numbers[i]
		r_sum -= numbers[i]
		if l_sum == r_sum:
			return 1 + max(get_points(numbers[:i + 1], l_sum), get_points(numbers[i + 1:], r_sum))
	return 0
for test_case in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	print(get_points(a, sum(a)))


testcases = int(input())

def find_partition(ar, p, q):
	x = q + 1
	total = sum(ar[p:x])
	left_sum = 0
	right_sum = total
	index = p - 1
	while p <= q:
		if left_sum == right_sum:
			return index
		left_sum = left_sum + ar[p]
		right_sum = right_sum - ar[p]
		p = p + 1
		index = index + 1
	return -1

def find_score(ar, p, q):
	if p >= q:
		return 0
	part = find_partition(ar, p, q)
	if part == -1:
		return 0
	return 1 + max(find_score(ar, p, part), find_score(ar, part + 1, q))
while testcases > 0:
	n = int(input())
	input_array = input().split()
	ar = []
	for data in input_array:
		ar.append(int(data))
	if sum(ar) == 0:
		print(n - 1)
	else:
		print(find_score(ar, 0, len(ar) - 1))
	testcases = testcases - 1


from sys import stdin
t = int(stdin.readline())

def solution(l):
	if l == []:
		return 0
	if l == [0 for i in range(len(l))]:
		return len(l) - 1
	sommeMax = sum(l)
	if sommeMax % 2 == 1:
		return 0
	sommeCourante = 0
	ind = 0
	while sommeCourante < sommeMax / 2:
		sommeCourante += l[ind]
		ind += 1
	if sommeCourante == sommeMax / 2:
		return max(1 + solution(l[0:ind]), 1 + solution(l[ind:]))
	return 0
while t > 0:
	n = int(stdin.readline())
	elements = list(map(int, stdin.readline().split(' ')))
	print(solution(elements))
	t -= 1


def findPartitionIndex(A):
	A_sum = sum(A)
	if A_sum % 2 != 0:
		return None
	half_sum = A_sum / 2
	cur_sum = A[0]
	for i in range(1, len(A)):
		if cur_sum == half_sum:
			return i
		cur_sum += A[i]
	return None

def play(A):
	if not A:
		return 0
	if sum(A) == 0:
		return len(A) - 1
	part_i = findPartitionIndex(A)
	if part_i:
		return 1 + max(play(A[:part_i]), play(A[part_i:]))
	else:
		return 0

def main():
	for _ in range(int(input())):
		input()
		A = [int(e) for e in input().split()]
		print(play(A))
	return
main()


from collections import defaultdict

class Accessor:

	def __init__(self, data, bot=0, top=float('inf')):
		self.data = data
		self.bot = bot
		self.top = top
		if self.top == float('inf'):
			self.top = len(data)

	def __getitem__(self, index):
		trueindex = index + self.bot
		if trueindex >= self.top:
			raise IndexError('Access by index out of bounds')
		return self.data[trueindex]

	def __len__(self):
		return self.top - self.bot

	def __str__(self):
		return str(self.data) + str(self.bot) + str(self.top)

class RunningSumCompWrapper:

	def __init__(self, running):
		self.running = running

	def __getitem__(self, index):
		sum_bot = self.running[index] - self.running[0]
		sum_top = self.running[len(self.running) - 1] - self.running[index]
		return sum_bot - sum_top

	def __len__(self):
		return len(self.running)

	def __str__(self):
		return str([self[i] for i in range(len(self))])

def binary_search(running, low=0, high=float('inf')):
	high = min(len(running) - 1, high)
	found = False
	while low <= high:
		i = (high + low) // 2
		x = running[i]
		if x < 0:
			low = i + 1
		elif x > 0:
			high = i - 1
		elif x == 0:
			found = True
			break
	return (i, found)

def binary_search_bounds(running, low=0, high=float('inf')):
	high = min(len(running) - 1, high)
	(high, found) = binary_search_upper(running, low, high)
	if found:
		(low, found) = binary_search_lower(running, low, high)
	return (low, high, found)

def binary_search_lower(running, low=0, high=float('inf')):
	high = min(len(running) - 1, high)
	found = False
	while low <= high:
		i = (high + low) // 2
		x = running[i]
		if x < 0:
			low = i + 1
		elif x > 0:
			high = i - 1
		elif x == 0:
			found = True
			high = i - 1
	return (low, found)

def binary_search_upper(running, low=0, high=float('inf')):
	high = min(len(running) - 1, high)
	found = False
	while low <= high:
		i = (high + low) // 2
		x = running[i]
		if x < 0:
			low = i + 1
		elif x > 0:
			high = i - 1
		elif x == 0:
			found = True
			low = i + 1
	return (high, found)

def solve_recur_helper(arr, bot, top, running):
	if top - bot < 1:
		return 0
	running_wrap = RunningSumCompWrapper(Accessor(running, bot, top + 2))
	(low, high, found) = binary_search_bounds(running_wrap, 1, top - bot)
	if not found:
		return 0
	val1 = solve_recur_helper(arr, bot, bot + low - 1, running)
	val2 = solve_recur_helper(arr, bot + high, top, running)
	mx = max(val1 + 1, val2 + 1)
	return mx

def make_running(arr):
	running = [0]
	for i in range(len(arr)):
		running.append(running[i] + arr[i])
	return running

def solve_recur(arr):
	running = make_running(arr)
	if running[-1] == 0:
		return len(arr) - 1
	return solve_recur_helper(arr, 0, len(arr) - 1, running)

def judge():
	tests = int(input())
	for i in range(tests):
		arr_sz = int(input())
		arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
		print(solve_recur(arr))
judge()


T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	A = list(map(int, input().strip().split()))
	S = A * 1
	H = {S[0]: 0}
	for i in range(1, N):
		S[i] += S[i - 1]
		H[S[i]] = i
	anchors = set()
	anchors.add(0)
	score = 0
	if S[-1] == 0:
		score = N - 1
	elif S[-1] % 2 == 0:
		offset = S[-1] / 2
		while anchors:
			for a in anchors.copy():
				if offset + a in H:
					anchors.add(a + offset)
				else:
					anchors.remove(a)
			if anchors:
				score += 1
			if offset % 2 == 0:
				offset /= 2
			else:
				anchors = None
	print(score)


def score(a):
	n = len(a)
	if n == 1:
		return 0
	else:
		left = 0
		right = n
		index = int((left + right) / 2)
		eqflag = 0
		while right - left > 1:
			if sum(a[0:index]) == sum(a[index:n]):
				eqflag = 1
				break
			elif sum(a[0:index]) > sum(a[index:n]):
				right = index
				index = int((left + right) / 2)
			elif sum(a[0:index]) < sum(a[index:n]):
				left = index
				index = int((left + right) / 2)
		if eqflag == 0:
			return 0
		else:
			return 1 + max(score(a[0:index]), score(a[index:n]))
t = int(input())
for i in range(0, t):
	n = int(input())
	a = [int(ai) for ai in input().split()]
	if sum(a) == 0:
		print(n - 1)
	else:
		print(score(a))


import sys

def sum_between(A, x, y):
	if x == 0:
		return A[y]
	else:
		return A[y] - A[x - 1]

def _splitting_game(A, x, y):
	i = x
	while i <= y and sum_between(A, x, i) != sum_between(A, i + 1, y):
		i += 1
	if i == x and A[x] == 0:
		return len(A) - 1
	if i >= y + 1:
		return 0
	else:
		return 1 + max(_splitting_game(A, x, i), _splitting_game(A, i + 1, y))

def splitting_game(A):
	sums = [x for x in A]
	for i in range(1, len(A)):
		sums[i] += sums[i - 1]
	return _splitting_game(sums, 0, len(A) - 1)
t = int(input())
for _ in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	print(splitting_game(A))


import sys
sys.setrecursionlimit(65536)
t = int(input())

def solve(a, start, stop, total):
	length = stop - start + 1
	if total % 2 == 1 or length == 1:
		return 0
	first_half_sum = a[start]
	first_half_index = start
	while first_half_sum * 2 < total:
		first_half_index += 1
		first_half_sum += a[first_half_index]
	if first_half_sum * 2 == total:
		return max(solve(a, start, first_half_index, total // 2), solve(a, first_half_index + 1, stop, total // 2)) + 1
	return 0
for testcase in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	print(solve(a, 0, len(a) - 1, sum(a)))


import sys
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	sum_left = [0 for x in range(N)]
	sum_right = sum_left[:]
	sum_left[0] = A[0]
	sum_right[N - 1] = A[N - 1]
	for i in range(1, N):
		sum_left[i] = A[i] + sum_left[i - 1]
		sum_right[N - i - 1] = A[N - i - 1] + sum_right[N - i]

	def dp_recursive(s, n):
		point = 0
		left_minus = sum_left[s - 1] if s - 1 >= 0 else 0
		right_minus = sum_right[n] if n < N else 0
		for i in range(s, n - 1):
			if sum_left[i] - left_minus == sum_right[i + 1] - right_minus:
				point = 1 + max(dp_recursive(s, i + 1), dp_recursive(i + 1, n))
				break
		return point
	print(dp_recursive(0, N))


def splitArray(a):
	x = len(a)
	if x == 1:
		return 0
	if max(a) == 0:
		return x - 1
	p = 0
	q = 0
	s = 0
	t = x - 1
	p += a[s]
	q += a[t]
	split = True
	if x > 2:
		while t > s:
			if p > q:
				t -= 1
				if t == s:
					split = False
					break
				q += a[t]
			elif p < q:
				s += 1
				if t == s:
					split = False
					break
				p += a[s]
			else:
				if t == s + 2:
					if a[t - 1] > 0:
						split = False
					break
				t -= 1
				if t == s:
					split = False
					break
				s += 1
				if t == s:
					split = False
					break
				q += a[t]
				p += a[s]
			if t == s + 1:
				break
	ret = 0
	if split == True and p == q:
		ret = 1
		ret += max(splitArray(a[:t]), splitArray(a[t:]))
	return ret
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	s = splitArray(a)
	print(s)


def bb(a):
	if len(a) < 2:
		return 0
	s = sum(a)
	x = 0
	for i in range(len(a) - 1):
		x += a[i]
		if x == s / 2:
			return 1 + max(bb(a[:i + 1]), bb(a[i + 1:]))
	return 0
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) == 0:
		print(n - 1)
	else:
		print(bb(a))


import sys

def nikita(arr):
	if len(arr) <= 1:
		return 0
	sum_arr = [arr[0]]
	for num in arr[1:]:
		sum_arr.append(sum_arr[-1] + num)
	if sum_arr[-1] == 0:
		return len(arr) - 1
	for idx in range(len(sum_arr)):
		if sum_arr[-1] > 0 and sum_arr[idx] > 0 and (sum_arr[-1] / sum_arr[idx] == 2):
			p1_sum = nikita(arr[:idx + 1])
			p2_sum = nikita(arr[idx + 1:])
			return max(p1_sum, p2_sum) + 1
	return 0
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	q = [int(q_temp) for q_temp in input().strip().split(' ')]
	print(nikita(q))


def find_count(ar, n):
	flag = 0
	if n == 1:
		return 0
	ar1 = [None for i in range(n)]
	temp = 0
	for j in range(n):
		ar1[j] = temp + ar[j]
		temp = ar1[j]
	if ar1[n - 1] == 0:
		return n - 1
	for i in range(n):
		if ar1[i] == ar1[n - 1] - ar1[i] and flag == 0:
			flag = 1
			return 1 + max(find_count(ar[:i + 1], i + 1), find_count(ar[i + 1:], n - i - 1))
	if flag == 0:
		return 0
t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	print(find_count(ar, n))


import bisect

def solve(nums):
	sums = [nums[0]]
	for num in nums[1:]:
		sums.append(sums[-1] + num)
	if sums[-1] == 0:
		return len(nums) - 1

	def get_range_sum(start, end):
		return sums[end - 1] - (0 if start == 0 else sums[start - 1])

	def get_max_scores(start, end):
		range_sum = get_range_sum(start, end)
		if range_sum % 2 != 0:
			return 0
		section = bisect.bisect_right(sums, (0 if start == 0 else sums[start - 1]) + range_sum // 2, start, end)
		if get_range_sum(start, section) == range_sum // 2:
			return 1 + max(get_max_scores(start, section), get_max_scores(section, end))
		else:
			return 0
	return get_max_scores(0, len(nums))
num_cases = int(input())
for case_idx in range(num_cases):
	n = int(input())
	nums = list(map(int, input().split()))
	print(solve(nums))


def isThere(B):
	N = len(B)
	s = 0
	S = [0] * N
	for i in range(N):
		s += B[i]
		S[i] = s
	if S[-1] % 2:
		return 0
	elif S[-1] == 0:
		return N - 1
	elif S[-1] // 2 in S:
		i = S.index(S[-1] // 2)
		return 1 + max(isThere(B[:i + 1]), isThere(B[i + 1:]))
	else:
		return 0
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(isThere(A))


def calc_val(iput):
	if len(iput) == 1:
		return 0
	pt = 0
	sum_l = iput[0]
	sum_r = sum(iput[1:])
	for j in range(1, len(iput)):
		if j == 0:
			continue
		if sum_l == sum_r:
			pt = 1 + max(calc_val(iput[j:]), calc_val(iput[:j]))
			break
		if sum_l != sum_r:
			sum_l += iput[j]
			sum_r -= iput[j]
	return pt

def main():
	t_case = input()
	t_case = int(t_case)
	listolist = []
	pnt = []
	for j in range(t_case):
		size = input()
		size = int(size)
		inp = input()
		list1 = inp.split()
		list1 = [int(e) for e in list1]
		listolist.append(list1)
		list1 = []
	for j in listolist:
		if sum(j) == 0:
			pnt.append(len(j) - 1)
		else:
			pnt.append(calc_val(j))
	for k in pnt:
		print(k)
main()


from bisect import bisect_left, bisect_right

def solve(A):
	S = [0]
	for a in A:
		S.append(S[-1] + a)

	def getMax(a, b):
		if a == b:
			return bisect_right(S, b) - bisect_left(S, a) - 2
		c = (a + b) / 2
		if int(c) == c and S[bisect_left(S, c)] == c:
			return max(getMax(a, c), getMax(c, b)) + 1
		return 0
	return getMax(0, S[-1])
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve(A))


import sys
import os

def solve_game(N, A):
	sum_lr = list()
	sum_lr.append(A[0])
	for i in range(1, N):
		sum_lr.append(sum_lr[i - 1] + A[i])
	out = search_game(sum_lr)
	return out

def search_game(sum_lr):
	if len(set(sum_lr)) == 1:
		return len(sum_lr) - 1
	sum_lrs = set(sum_lr)
	half = sum_lr[-1] / 2
	if half in sum_lrs:
		idx = sum_lr.index(half)
		left = sum_lr[0:idx + 1]
		right = sum_lr[idx + 1:]
		right = [x - half for x in right]
		return 1 + max(search_game(left), search_game(right))
	else:
		return 0
sys.setrecursionlimit(1000)
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	A = [int(q_temp) for q_temp in input().strip().split(' ')]
	out = solve_game(N, A)
	print(out)


def find_sum(arr, n):
	if n <= 1:
		return 0
	temp = [0 for i in range(n)]
	temp[0] = arr[0]
	for i in range(1, n):
		temp[i] = temp[i - 1] + arr[i]
	if temp[n - 1] == 0:
		return n - 1
	else:
		flag = 0
		i = 0
		while i < n - 1:
			if temp[n - 1] - temp[i] == temp[i]:
				flag = 1
				break
			else:
				i += 1
		if flag == 1:
			return 1 + max(find_sum(arr[:i + 1], i + 1), find_sum(arr[i + 1:n], n - i - 1))
		else:
			return 0
t = int(input())
for a0 in range(t):
	n = int(input())
	arr = [int(a_temp) for a_temp in input().split()]
	count = find_sum(arr, n)
	print(count)


import sys
sys.setrecursionlimit(10 ** 5)

def divide(l):
	if len(set(l)) == 1:
		if set(l) == {0}:
			return len(l) - 1
		elif len(l) % 2 == 0:
			return 1 + divide(l[:int(len(l) / 2)])
		else:
			return 0
	if len(l) == 1 or l == []:
		return 0
	tsum = sum(l)
	p = 0
	divided = False
	for i in range(len(l)):
		p += l[i]
		if p == tsum - l[i]:
			divided = True
			return 1 + max(divide(l[:i + 1]), divide(l[i + 1:len(l)]))
		else:
			tsum -= l[i]
	return 0
for i in range(int(input())):
	int(input())
	print(divide([int(x) for x in input().split()]))


a = [4, 1, 0, 1, 1, 0, 1]

def devide(a):
	su = sum(a)
	if su % 2 == 1 or len(a) < 2:
		return (-1, [0], [0])
	else:
		s = 0
		for i in range(len(a)):
			s = s + a[i]
			if s == su // 2:
				return (1, a[0:i + 1], a[i + 1:len(a)])
	return (-1, [0], [0])

def get_step(a):
	li1 = []
	li1.append(a)
	i = 0
	j = []
	while 1:
		li2 = []
		for j in li1:
			if j is not None and len(j) > 1:
				(b, c, d) = devide(j)
				if b == -1:
					continue
				else:
					li2.append(c)
					li2.append(d)
		li1 = li2[:]
		if len(li1) < 1:
			break
		i += 1
	return i
la = []
a = int(input())
for i in range(a):
	b = int(input())
	inp = input().split()
	c = []
	for i in inp:
		c.append(int(0 if i is None else int(i)))
	if c is not None:
		la.append(get_step(c))
for i in la:
	print(i)


T = int(input())

def do_the_things(A_list, big_sum):
	_sum = 0
	count = 0
	slice_A = []
	slice_B = []
	if big_sum == 0:
		return len(A_list) - 1
	for i in A_list:
		_sum += i
		if _sum == big_sum / 2:
			slice_A = do_the_things(A_list[:count + 1], _sum)
			slice_B = do_the_things(A_list[count + 1:], _sum)
			if slice_A >= slice_B:
				return 1 + slice_A
			else:
				return 1 + slice_B
		count += 1
	return 0
for i in range(T):
	points = 0
	big_sum = 0
	N = int(input())
	A = [int(q_temp) for q_temp in input().strip().split(' ')]
	for o in A:
		big_sum += o
	print(do_the_things(A, big_sum))


def nikita(arr):
	n = len(arr)
	h = {}
	cum_sum = 0
	for (i, a) in enumerate(arr):
		cum_sum += a
		h[cum_sum] = i
	if not cum_sum:
		p = n - 1
	else:
		p = nikitaRec(arr, h, cum_sum, 0, -1)
	print(p)

def nikitaRec(arr, h, target, offset, i_offset):
	if len(arr) <= 1:
		return 0
	if len(arr) == 2:
		return 1 if arr[0] == arr[1] else 0
	if target % 2:
		return 0
	p = 0
	key = offset + int(target / 2)
	if key in h.keys():
		(p_left, p_right) = (0, 0)
		i = h[key]
		if i - i_offset > 1:
			p_left = nikitaRec(arr, h, target / 2, offset, i_offset)
		if i != i_offset:
			p_right = nikitaRec(arr, h, target / 2, key, i)
		p = max(p_left + 1, p_right + 1)
	return p
T = int(input())
while T:
	n = int(input())
	arr = [int(s) for s in input().split()]
	nikita(arr)
	T -= 1


def findSplit(A):
	Lsum = 0
	Lind = -1
	Rsum = 0
	Rind = len(A)
	splits = 0
	while Rind - Lind > 1:
		if Lsum <= Rsum:
			Lind += 1
			Lsum += A[Lind]
		else:
			Rind -= 1
			Rsum += A[Rind]
	if Rsum == Lsum:
		splits = 1
		Lsplits = 0
		Rsplits = 0
		if Lind >= 1:
			if Lsum != 0:
				Lsplits = findSplit(A[0:Lind + 1])
			else:
				return len(A) - 1
		if Rind <= len(A) - 2:
			Rsplits = findSplit(A[Rind:])
		splits += max(Lsplits, Rsplits)
	return splits
T = int(input())
for i in range(0, T):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(findSplit(A))


t = int(input())

def partition(a, s, e, rightMax):
	p = s - 1
	for i in range(s + 1, e):
		while True:
			sum1 = 0
			sum2 = 0
			if p + 1 >= 0:
				sum2 = rightMax[i] - rightMax[p + 1]
			else:
				sum2 = rightMax[i]
			if s - 1 >= 0:
				sum1 = rightMax[p + 1] - rightMax[s - 1]
			else:
				sum1 = rightMax[p + 1]
			if sum1 < sum2:
				p += 1
				continue
			elif sum1 == sum2:
				p += 1
				break
			else:
				break
	ans = 0
	for i in range(s, p + 1):
		ans += a[i]
	ans2 = 0
	for i in range(p + 1, e):
		ans2 += a[i]
	if ans == ans2:
		return p
	else:
		return -1

def score(a, s, e, rightMax):
	if e - s <= 1:
		return 0
	p = partition(a, s, e, rightMax)
	if p == -1:
		return 0
	else:
		f1 = score(a, s, p + 1, rightMax)
		f2 = score(a, p + 1, e, rightMax)
		return 1 + max(f1, f2)
for z in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if sum(a) == 0:
		print(n - 1)
		continue
	rightMax = [0] * len(a)
	rightMax[0] = a[0]
	for i in range(1, n):
		rightMax[i] = rightMax[i - 1] + a[i]
	print(score(a, 0, n, rightMax))


import sys

def calculateSubSum(data):
	n = len(data)
	dp = [0 for x in range(n)]
	sum = 0
	for i in range(n):
		sum += data[i]
		dp[i] = sum
	return dp

def getSum(dp, i, k):
	if i > 0:
		return dp[k] - dp[i - 1]
	else:
		return dp[k]

def hasPartition(data, dp, i, j):
	for k in range(i, j):
		if getSum(dp, i, k) == getSum(dp, k + 1, j):
			if getSum(dp, i, k) == 0:
				return k + 1
			else:
				return k
	return -1

def splitScore(data, dp, i, j):
	if i == j:
		return 0
	else:
		k = hasPartition(data, dp, i, j)
		if k != -1:
			return 1 + max(splitScore(data, dp, i, k), splitScore(data, dp, k + 1, j))
	return 0
cases = int(input())
for k in range(cases):
	sys.setrecursionlimit(pow(2, 18))
	n = int(input())
	data = list(map(int, input().split(' ')))
	if sum(data) == 0:
		print(len(data) - 1)
	else:
		dp = calculateSubSum(data)
		print(splitScore(data, dp, 0, n - 1))


import sys

def solve(a, debug=0):
	cache = [0]
	sm = 0
	for v in a:
		sm += v
		cache.append(sm)
	if debug > 0:
		print(cache, file=sys.stderr)

	def partition_bf(fr, to):
		if to - fr < 2:
			return None
		(s1, s2) = (0, cache[to] - cache[fr])
		for i in range(fr, to):
			s1 += a[i]
			s2 -= a[i]
			if debug > 1:
				print(i, s1, s2, file=sys.stderr)
			if s1 == s2:
				return i + 1
		return None

	def partition(fr, to):
		if to - fr < 2:
			return None
		m_hist = set()
		m = (fr + to) // 2
		m_hist.add(m)
		while m not in (fr, to):
			(s1, s2) = (cache[m] - cache[fr], cache[to] - cache[m])
			if debug > 1:
				print(sorted(m_hist), file=sys.stderr)
				print('fr=%d m=%d to=%d' % (fr, m, to), file=sys.stderr)
				print('s1=%d s2=%d' % (s1, s2), file=sys.stderr)
			if s1 == s2:
				return m
			if s1 < s2:
				new_m = (m + to) // 2
			else:
				new_m = (fr + m) // 2
			if new_m == m or new_m in m_hist:
				break
			m = new_m
			m_hist.add(m)
		return None
	max_score = 0
	stack = [(0, (0, len(a)))]
	while stack:
		(score, interval) = stack.pop()
		max_score = max(score, max_score)
		(fr, to) = interval
		m = partition_bf(fr, to)
		if debug > 0:
			print('fr=%d m=%s to=%d score=%d max_score=%d' % (fr, m, to, score, max_score), file=sys.stderr)
		if m is not None:
			stack.append((score + 1, (fr, m)))
			stack.append((score + 1, (m, to)))
	return max_score
t = int(input())
debug = 0
for _ in range(t):
	_ = int(input())
	a = list(map(int, input().split()))
	if debug > 0:
		print('----------', file=sys.stderr)
	print(solve(a, debug))


T = int(input())
while T > 0:
	N = int(input())
	A = list(map(int, input().strip().split(' ')))
	score = 0
	fsum = A * 1
	h = {fsum[0]: 0}
	for i in range(1, N):
		fsum[i] += fsum[i - 1]
		h[fsum[i]] = i
	anchors = {0: True}
	if fsum[-1] == 0:
		score = N - 1
	elif fsum[-1] % 2 == 0:
		offset = fsum[-1] // 2
		while anchors:
			for a in list(anchors.keys()):
				if a + offset in h:
					anchors[a + offset] = True
				else:
					del anchors[a]
			if anchors:
				score += 1
			if offset % 2 == 0:
				offset = offset // 2
			else:
				anchors = None
	print(score)
	T -= 1


import sys

class Tree:
	left = None
	right = None
	val = None

	def __init__(self, val):
		self.val = val

def maxDepth(tree):
	if tree.val:
		ldepth = maxDepth(tree.left)
		rdepth = maxDepth(tree.right)
		if ldepth > rdepth:
			return ldepth + 1
		else:
			return rdepth + 1
	else:
		return 0

def play(arr, tree):
	total = sum(arr)
	half = total // 2
	length = len(arr)
	tempsum = 0
	splittable = False
	if total % 2 == 1 or length == 1:
		splittable = False
	else:
		for i in range(length):
			tempsum += arr[i]
			if tempsum == half:
				splittable = True
				break
			if tempsum > half:
				splittable = False
				break
	if splittable:
		tree.val = 1
		tree.left = Tree(0)
		tree.right = Tree(0)
		play(arr[0:i + 1], tree.left)
		play(arr[i + 1:], tree.right)
T = int(input())
sys.setrecursionlimit(3000)
for i in range(T):
	n = int(input())
	arr = [int(item) for item in input().split()]
	tree = Tree(0)
	if sum(arr) == 0:
		ans = len(arr) - 1
	else:
		play(arr, tree)
		ans = maxDepth(tree)
	print(ans)


def fun(s, sum_right):
	sum_left = 0
	n = len(s)
	if n == 1:
		return 0
	if sum_right == 0:
		return n - 1
	for i in range(n):
		sum_left += s[i]
		sum_right -= s[i]
		if sum_left == sum_right:
			return 1 + max(fun(s[:i + 1], sum_left), fun(s[i + 1:], sum_right))
	return 0
for test_case in range(int(input().strip())):
	n = int(input().strip())
	s = list(map(int, input().strip().split(' ')))
	print(fun(s, sum(s)))


def solve(N, A):
	total = sum(A)
	Q = [(0, N, total, 0)]
	answer = 0
	while Q:
		(i, j, t, d) = Q.pop()
		(halft, rt) = divmod(t, 2)
		if rt == 0:
			s = A[i]
			for k in range(i + 1, j):
				if s > halft:
					if d > answer:
						answer = d
					break
				if s == halft:
					Q.append((i, k, halft, d + 1))
					Q.append((k, j, halft, d + 1))
					break
				s += A[k]
		if d > answer:
			answer = d
	return answer
T = int(input())
for test in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	print(solve(N, A))


def rng_sm(l, s=0, e=None):
	if e == None:
		e = len(l) - 1
	sm = 0
	while s <= e:
		sm += l[s]
		s += 1
	return sm

def eq_sm_idx(l, s=0, e=None):
	arr_len = len(l)
	if arr_len <= 1:
		return -1
	if e == None:
		e = arr_len - 1
	(m1, m2) = (s, e)
	m = (m1 + m2) // 2
	while True:
		m_prev = m
		lsum = rng_sm(l, s, m)
		rsum = rng_sm(l, m + 1, e)
		if lsum == rsum:
			break
		elif lsum > rsum:
			m2 = m
			m = (m1 + m2) // 2
		else:
			m1 = m
			m = (m1 + m2) // 2
		if m == m_prev:
			break
	if m != e and rng_sm(l, s, m) == rng_sm(l, m + 1, e):
		return m
	else:
		return -1

def num_arr_splits(l):
	if rng_sm(l) == 0:
		return len(l) - 1
	eq_idx = eq_sm_idx(l)
	if eq_idx == -1:
		return 0
	elif len(l) == 2:
		return 1
	else:
		return max(1 + num_arr_splits(l[:eq_idx + 1]), 1 + num_arr_splits(l[eq_idx + 1:]))
t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(num_arr_splits(l))


def bestScore(start, end, totalSum):
	sumRight = totalSum
	sumLeft = 0
	k = start
	while sumRight > sumLeft:
		sumLeft += A[k]
		sumRight -= A[k]
		k += 1
	if sumRight == sumLeft:
		return 1 + max(bestScore(start, k, sumLeft), bestScore(k, end, sumRight))
	else:
		return 0
t = int(input())
A = []
for j in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	if sum(A) == 0:
		print(N - 1)
	else:
		print(bestScore(0, N, sum(A)))


def find_score_private(numbers, start, end):
	if end - start < 2:
		return 0
	split_index = find_split_index(numbers, start, end)
	if split_index is None:
		return 0
	return max(find_score_private(numbers, start, split_index), find_score_private(numbers, split_index, end)) + 1

def find_split_index(numbers, start, end):
	index = start
	first_half = 0
	second_half = 0
	for i in range(start, end):
		second_half += numbers[i]
	while index < end:
		first_half += numbers[index]
		second_half -= numbers[index]
		index += 1
		if first_half == second_half:
			return index

def find_score(numbers, N):
	if sum(numbers) == 0:
		return N - 1
	return find_score_private(numbers, 0, N)
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	numbers = [int(x) for x in input().strip().split()]
	print(find_score(numbers, N))


def best_score(a):
	max_depth = 0
	queue = [(a, 0)]
	while queue:
		(S, depth) = queue.pop(0)
		split = False
		left_sum = sum(S)
		right_sum = 0
		for i in range(len(S) - 1, 0, -1):
			left_sum -= S[i]
			right_sum += S[i]
			if left_sum == right_sum:
				split = True
				depth += 1
				queue.append((S[:i], depth))
				queue.append((S[i:], depth))
				break
		if not split:
			if depth > max_depth:
				max_depth = depth
	return max_depth

def main():
	num_tests = int(input())
	for _ in range(num_tests):
		input()
		a = [int(n) for n in input().split()]
		if a[0] == 0 and len(set(a)) == 1:
			print(len(a) - 1)
		else:
			print(best_score(a))
main()


def opt(a, i, j):
	if i == j:
		return 0
	else:
		ii = i
		total = sum(a[i:j + 1])
		left = a[i]
		while left << 1 != total and i + 1 < j:
			i += 1
			left += a[i]
		if left << 1 == total and i < j:
			return 1 + max(opt(a, ii, i), opt(a, i + 1, j))
		else:
			return 0
n = int(input())
for each in range(n):
	s = int(input())
	a = list(map(int, input().split()))
	if sum(a) == 0:
		print(s - 1)
	else:
		print(opt(a, 0, s - 1))


def nikita(arg_array):
	len_array = len(arg_array)
	if len_array == 0 or len_array == 1:
		return 0
	sum_array = sum(arg_array)
	if sum_array % 2 == 1:
		return 0
	if sum_array == 0:
		return len_array - 1
	acc = 0
	for i in range(len_array):
		acc += arg_array[i]
		if acc == sum_array // 2:
			return 1 + max(nikita(arg_array[:i + 1]), nikita(arg_array[i + 1:]))
	return 0
t = int(input())
for test in range(0, t):
	arraySize = int(input())
	array = list(map(int, input().split()))
	print(nikita(array))


def partition(arr, lo, hi):
	arr_sum = sum(arr[lo:hi])
	if arr_sum == 0:
		return hi - lo - 1
	elif arr_sum % 2 == 1:
		return 0
	else:
		arr_acc = 0
		arr_sum //= 2
		for index in range(lo, hi):
			arr_acc += arr[index]
			if arr_acc == arr_sum:
				index += 1
				return 1 + max(partition(arr, lo, index), partition(arr, index, hi))
			elif arr_acc > arr_sum:
				return 0
t = int(input().strip())
for test in range(t):
	n = int(input().strip())
	a = [int(s) for s in input().strip().split()]
	print(partition(a, 0, n))


def solve(nums):
	if not nums or len(nums) == 1:
		return 0
	sofar = 0
	other = sum(nums)
	if other == 0:
		return len(nums) - 1
	for (i, num) in enumerate(nums):
		if sofar == other:
			return 1 + max([solve(nums[:i]), solve(nums[i:])])
		else:
			sofar += num
			other -= num
	return 0
for _ in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	print(solve(nums))


import sys
import math

def split_array(array, splits_so_far):
	(target_sum, r) = divmod(sum(array), 2)
	if r != 0:
		return splits_so_far
	elif target_sum == 0:
		return splits_so_far + len(array) - 1
	else:
		i = 0
		current_sum = 0
		while current_sum < target_sum and i < len(array):
			current_sum += array[i]
			i += 1
		if current_sum == target_sum:
			return max(split_array(array[:i], splits_so_far + 1), split_array(array[i:], splits_so_far + 1))
		else:
			return splits_so_far
test_cases = int(sys.stdin.readline())
for _ in range(test_cases):
	array_len = int(sys.stdin.readline())
	array = list(map(int, sys.stdin.readline().split()))
	print(split_array(array, 0))


import sys

def find_split(start, end, nums, depth):
	if len(nums[start:end]) == 1:
		return depth
	_sum = sum(nums[start:end])
	if _sum % 2 == 1:
		return depth
	if _sum == 0:
		return depth + len(nums[start:end]) - 1
	running_sum = 0
	for i in range(start, end):
		running_sum += nums[i]
		if running_sum == _sum / 2:
			depth = max(find_split(start, i + 1, nums, depth + 1), find_split(i + 1, end, nums, depth + 1))
			break
		elif running_sum > _sum / 2:
			break
	return depth
num_test = int(input())
for test_id in range(num_test):
	n = int(input())
	nums = list(map(int, input().strip().split()))
	if n == 0:
		print(0)
		continue
	depth = find_split(0, n, nums, 0)
	print(depth)


def binaryPartitions(array):
	sumArray = []
	runningSum = 0
	for num in array:
		runningSum += num
		sumArray.append(runningSum)
	return __binaryPartitions(array, sumArray)

def __binaryPartitions(array, sumArray):
	if len(sumArray) < 2:
		return 0
	beg = sumArray[0] - array[0]
	end = sumArray[-1]
	target = (beg + end) / 2
	if target == 0:
		return len(sumArray) - 1
	lf = 0
	rt = len(sumArray) - 1
	while lf <= rt:
		mid = int((lf + rt) / 2)
		midVal = sumArray[mid]
		if target == midVal:
			return 1 + max(__binaryPartitions(array[:mid + 1], sumArray[:mid + 1]), __binaryPartitions(array[mid + 1:], sumArray[mid + 1:]))
		elif target < midVal:
			rt = mid - 1
		else:
			lf = mid + 1
	return 0
T = int(input())
outputs = []
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().strip().split(' ')]
	outputs.append(binaryPartitions(A))
for output in outputs:
	print(output)


from collections import deque
from fileinput import input

class Solver:

	def __init__(self):
		N = int(next(data))
		self.t = tuple(map(int, next(data).split()))
		total = sum(self.t)
		if total == 0:
			print(N - 1)
		else:
			print(self.score(0, N, total))

	def score(self, b, e, total):
		if total == 0:
			return e - b - 1
		elif total % 2 == 1:
			return 0
		elif b + 1 < e:
			l_sum = 0
			target = total / 2
			for i in range(b, e - 1):
				l_sum += self.t[i]
				if l_sum > target:
					return 0
				if l_sum == target:
					return max(self.score(b, i + 1, target), self.score(i + 1, e, target)) + 1
			return 0
		else:
			return 0
data = input()
T = int(next(data))
for case in range(T):
	Solver()


def memoize(func):
	cache = {}

	def wrapper(arg):
		if arg not in cache:
			cache[arg] = func(arg)
		return cache[arg]
	return wrapper

@memoize
def nikita_game_number(arr):
	if len(arr) <= 1:
		return 0
	if sum(arr) == 0:
		return len(arr) - 1
	left_sum = 0
	right_sum = sum(arr)
	for (idx, a) in enumerate(arr[:-1]):
		left_sum += a
		right_sum -= a
		if left_sum == right_sum:
			return 1 + max(nikita_game_number(arr[:idx + 1]), nikita_game_number(arr[idx + 1:]))
		if left_sum > right_sum:
			return 0
	return 0
T = int(input().strip())
for test in range(T):
	N = int(input().strip())
	A = tuple((int(x) for x in input().strip().split(' ')))
	print(nikita_game_number(A))


def max_moves(arr, total):
	half = total / 2
	curr = 0
	if total == 0:
		return len(arr) - 1
	elif total % 2 == 1:
		return 0
	for i in range(len(arr)):
		if curr == half:
			return max(max_moves(arr[:i], half), max_moves(arr[i:], half)) + 1
		elif curr > half:
			break
		curr = curr + arr[i]
	return 0
for _ in range(int(input())):
	N = input()
	A = [int(x) for x in input().split()]
	print(max_moves(A, sum(A)))


import copy

def get_csum_arr(arr):
	(csum_arr, s) = ([], 0)
	for e in arr:
		s += e
		csum_arr.append(s)
	return csum_arr

def _process(left, right):
	s = 0
	stack = [(1, left), (1, right)]
	max_level = 1
	while stack:
		(level, partition) = stack.pop()
		max_level = max(max_level, level)
		elem = partition[-1]
		if elem % 2 == 0:
			try:
				pivot = partition[:-1].index(elem // 2)
				left_partition = partition[:pivot + 1]
				right_partition = [e - elem // 2 for e in partition[pivot + 1:]]
				stack.extend([(level + 1, left_partition), (level + 1, right_partition)])
			except ValueError:
				pass
	return max_level

def _get_score(csum_arr):
	size = len(csum_arr)
	if size == 0:
		return 0
	elem = csum_arr[-1]
	if elem % 2 == 0:
		try:
			pivot = csum_arr[:-1].index(elem // 2)
			left_partition = csum_arr[:pivot + 1]
			right_partition = [e - elem // 2 for e in csum_arr[pivot + 1:]]
			return _process(left_partition, right_partition)
		except ValueError:
			return 0
	return 0

def get_score(arr):
	csum_arr = get_csum_arr(arr)
	return _get_score(csum_arr)
cases = int(input())
for _ in range(cases):
	(size, arr) = (int(input()), [int(i) for i in input().split()])
	print(get_score(arr))


def do_game(input):

	def split_arr(a):
		if len(a) < 2:
			return None
		left_pos = 0
		right_pos = len(a) - 1
		left_sum = a[left_pos]
		right_sum = a[right_pos]
		while right_pos - left_pos != 1:
			if left_sum < right_sum:
				left_pos += 1
				left_sum += a[left_pos]
			else:
				right_pos -= 1
				right_sum += a[right_pos]
		if left_sum == right_sum:
			return right_pos
		return None
	a = [int(s) for s in input.split(' ')]
	if all((i == 0 for i in a)):
		print(len(a) - 1)
		return
	max_depth = 0
	stack = [(max_depth, a)]
	while stack:
		(depth, a) = stack.pop()
		if depth > max_depth:
			max_depth = depth
		res = split_arr(a)
		if res is not None:
			stack.append((depth + 1, a[:res]))
			stack.append((depth + 1, a[res:]))
	print(max_depth)
cases = int(input())
for _ in range(cases):
	num = input()
	do_game(input())


def summation(l, r):
	return A[r] - A[l - 1]

def get(l, r, s):
	low = l
	high = r
	while low <= high:
		mid = (low + high) // 2
		x = summation(l, mid)
		if x == s and (mid == 1 or summation(l, mid - 1) != s):
			return mid
		elif x >= s:
			high = mid - 1
		else:
			low = mid + 1
	return -1

def helper(l, r):
	s = summation(l, r)
	if l != r and s % 2 == 0:
		ind = get(l, r, s // 2)
		if ind != -1:
			return max(helper(l, ind), helper(ind + 1, r)) + 1
	return 0
M = int(input())
for m in range(M):
	n = int(input())
	A = list(map(int, input().split(' ')))
	if all((v == 0 for v in A)):
		print(n - 1)
	else:
		A.insert(0, 0)
		for i in range(1, n + 1):
			A[i] += A[i - 1]
		print(helper(1, n))


from itertools import islice

class Nikita(object):
	cache = dict()

	def __init__(self, game_size, game_array):
		self.size = game_size
		self.array = game_array
		self.scan = self.sumscan(game_array)
		self.max_depth = 0
		if not game_array:
			self.max_depth = game_size - 1
		self.jobs = [(0, self.scan[-1], 0, len(self.array) + 1)]

	def run(self):
		while self.jobs:
			depth = self.run_job(*self.jobs.pop())
			if depth and depth > self.max_depth:
				self.max_depth = depth
		return self.max_depth

	def run_job(self, depth, chunk_sum, start, end):
		size = end - start
		if not size:
			return
		if size == 1:
			return depth
		if chunk_sum % 2:
			return depth
		if depth + size - 1 <= self.max_depth:
			return
		next_chunk_sum = chunk_sum // 2
		midpoint = self.scan[start] + next_chunk_sum
		enumerator = enumerate(islice(self.scan, start + 1, end), start + 1)
		for (index, value) in enumerator:
			if value > midpoint:
				break
			if value == midpoint:
				self.jobs.append((depth + 1, next_chunk_sum, start, index))
				self.jobs.append((depth + 1, next_chunk_sum, index, end))
		return depth

	@staticmethod
	def solve():
		num_games = int(input())
		games = [Nikita(int(input()), [int(value) for value in input().split() if value != '0']) for _ in range(num_games)]
		for game in games:
			print(game.run())

	@staticmethod
	def sumscan(array):

		def accumulate():
			accumulated = 0
			while True:
				accumulated += (yield accumulated)
		accumulator = accumulate()
		return [next(accumulator)] + [accumulator.send(n) for n in array]
Nikita.solve()


def solve(arr, s):
	s = s / 2
	if s == 0:
		if arr != [0] * len(arr):
			return 0
		else:
			return len(arr) - 1
	t = 0
	pos = -1
	if len(arr) <= 1:
		return 0
	for i in range(len(arr)):
		t += arr[i]
		if t == s:
			pos = i
			break
	if pos == -1:
		return 0
	return 1 + max(solve(arr[:pos + 1], s), solve(arr[pos + 1:], s))
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(a, sum(a)))


import sys

def maxScore(start, stop, n, arr, depth):
	s = sum(arr[start:stop])
	if stop - start <= 1:
		return depth
	if s == 0:
		return stop - start - 1
	s = s // 2
	curSum = 0
	if s == 0:
		return depth
	for i in range(start, stop):
		curSum += arr[i]
		if curSum == s:
			return max(maxScore(start, i + 1, n, arr, depth + 1), maxScore(i + 1, stop, n, arr, depth + 1))
	return depth
T = int(input().strip())
for i in range(T):
	n = int(input().strip())
	arr = input().strip().split()
	arr = [int(x) for x in arr]
	print(maxScore(0, n, n, arr, 0))


import sys
memo = {}
sys.setrecursionlimit(100000)

def find_part(ar, start, end):
	if start < end:
		tot = 0
		for i in range(start, end + 1):
			tot += ar[i]
		sub_tot1 = 0
		for i in range(start, end + 1):
			sub_tot1 += ar[i]
			sub_tot2 = tot - sub_tot1
			if sub_tot1 == sub_tot2:
				return i
	return -1

def max_points(ar, start, end):
	if (start, end) in memo:
		return memo[start, end]
	if (start, end) in memo:
		return memo[start, end]
	p = find_part(ar, start, end)
	if p != -1:
		memo[start, end] = 1 + max(max_points(ar, start, p), max_points(ar, p + 1, end))
		return memo[start, end]
	return 0
T = int(input())
for _ in range(T):
	memo = {}
	n = int(input())
	ar = list(map(int, input().split()))
	start = 0
	end = n - 1
	print(max_points(ar, start, end))


def num_splits(A):
	if len(A) < 2 or not sum(A):
		return len(A) - 1
	(i, total, mid) = (0, 0, sum(A) / 2)
	while i < len(A) and total < mid:
		total += A[i]
		i += 1
	if total == mid:
		return 1 + max(num_splits(A[:i]), num_splits(A[i:]))
	return 0
cases = int(input())
for i in range(cases):
	length = int(input())
	nums = [int(i) for i in input().split(' ')]
	print(num_splits(nums))


def findMid(arr):
	s = sum(arr)
	if s % 2 != 0:
		return 'err'
	if s == 0:
		return 'len'
	arrSum = 0
	for i in range(len(arr)):
		arrSum += arr[i]
		if arrSum == s / 2.0:
			return i
	return 'err'

def findRes(arr):
	index = findMid(arr)
	if index == 'err':
		return 0
	if index == 'len':
		return len(arr) - 1
	return max(findRes(arr[0:index + 1]) + 1, findRes(arr[index + 1:]) + 1)
res = []
test = int(input())
for i in range(test):
	length = int(input())
	arr = [int(x) for x in input().split(' ')]
	res.append(findRes(arr))
for i in res:
	print(i)


T = int(input())
import sys
rec_depth = 15

def splithalf(a):
	if len(a) < 2:
		return 0
	count = 0
	sum_left = a[0]
	sum_right = a[-1]
	j = 0
	k = len(a) - 1
	for i in range(len(a) - 2):
		if sum_left < sum_right:
			j += 1
			sum_left += a[j]
		else:
			k -= 1
			sum_right += a[k]
	if j + 1 == k and sum_left == sum_right:
		(x, y) = (0, 0)
		if j != 0:
			while a[j] == 0 and a[j + 1] == 0 and (j < len(a) - 2):
				j += 1
			x = splithalf(a[:j + 1])
		if k != len(a) - 1:
			while a[k] == 0 and a[k - 1] == 0 and (k > 2):
				k -= 1
			y = splithalf(a[k:])
		return 1 + max(x, y)
	else:
		return 0
for i in range(T):
	N = int(input())
	if N > rec_depth:
		rec_depth = int(N + N * 0.2)
		sys.setrecursionlimit(rec_depth)
	A = list(map(int, input().split()))
	allz = 1
	for i in A:
		if i != 0:
			allz = 0
			break
	if allz:
		print(N - 1)
	else:
		print(splithalf(A[:]))


def maxsplit(ar):
	if len(ar) < 2:
		return 0
	ar_total = sum(ar)
	if ar_total % 2 == 1:
		return 0
	if ar_total == 0 and all([x == 0 for x in ar]):
		return len(ar) - 1
	psum = 0
	for (i, el) in enumerate(ar):
		psum += el
		if psum == ar_total // 2:
			return max(maxsplit(ar[:i + 1]), maxsplit(ar[i + 1:])) + 1
		elif psum > ar_total // 2:
			return 0
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	ar = [int(x) for x in input().strip().split()]
	assert len(ar) == n
	print(maxsplit(ar))


n = int(input().strip())
memo = {}

def find_max_score(arr):
	if sum(arr) == 0:
		return len(arr) - 1
	part = check_part(arr, 0, len(arr) - 1)
	if part != -1:
		left_max = find_max_score(arr[:part])
		right_max = find_max_score(arr[part:])
		return 1 + max(left_max, right_max)
	else:
		return 0

def check_part(arr, a, b):
	idx = int((a + b) / 2 + 0.5)
	l_sum = sum(arr[:idx])
	r_sum = sum(arr[idx:])
	if len(arr) <= 1:
		return -1
	if sum(arr) == 0:
		return 1
	if a == b:
		return idx if l_sum == r_sum else -1
	if l_sum == r_sum:
		return idx
	elif l_sum < r_sum:
		new_idx = b if idx + 1 > b else idx + 1
		return check_part(arr, new_idx, b)
	else:
		new_idx = a if idx - 1 < a else idx - 1
		return check_part(arr, a, new_idx)
for i in range(n):
	trash = input()
	arr = [int(e) for e in input().strip().split(' ')]
	print(find_max_score(arr))


def check_points(a, points):
	n = len(a)
	sm = sum(a)
	if sm % 2 != 0 or n <= 1:
		return points
	sm = int(sm / 2)
	if sm > 0:
		s = 0
		i = 0
		while i < n and s < sm:
			s += a[i]
			i += 1
	else:
		return points + n - 1
	if s == sm:
		return max(check_points(a[:i], points + 1), check_points(a[i:], points + 1))
	else:
		return points
for t in range(int(input().strip())):
	N = int(input().strip())
	A = list(map(int, input().strip().split()))
	print(check_points(A, 0))


def party(a):
	if a != None:
		s = split(a)
		if s != 0:
			return 1 + max(party(a[:s]), party(a[s:]))
		else:
			return 0

def split(arr):
	x = 0
	y = len(arr) - 1
	s_a = 0
	s_b = 0
	while x <= y:
		if s_a == s_b:
			s_a += arr[x]
			x = x + 1
		elif s_a > s_b:
			s_b += arr[y]
			y = y - 1
		else:
			s_a += arr[x]
			x = x + 1
	if s_a == s_b:
		return x
	else:
		return 0
cases = int(input())
for q in range(cases):
	n = int(input())
	lis = list(map(int, input().split()))
	t = False
	for i in lis:
		if i > 0:
			t = True
			break
	if not t:
		print(n - 1)
	else:
		print(party(lis))


nb_cases = int(input())

def move(array, s, size):
	if size == 1:
		return 0
	count = 0
	if s == 0:
		return size - 1
	if s % 2 != 0:
		return 0
	half = s / 2
	tmp = 0
	for (i, el) in enumerate(array):
		tmp += el
		if tmp == half:
			count += 1
			if half % 2 != 0:
				break
			left = move(array[0:i + 1], half, i + 1)
			right = move(array[i + 1:size + 1], half, size - i - 1)
			if left > right:
				count += left
			else:
				count += right
			break
		elif tmp > half:
			return 0
	return count
for cases in range(nb_cases):
	array_size = int(input())
	s = 0
	array = []
	for el in input().split():
		array.append(int(el))
		s += int(el)
	res = move(array, s, array_size)
	print(res)


def partion(array, start, end, total):
	if total == 0:
		sols[start][end] = end - start - 1
		return end - start - 1
	if end in sols[start]:
		return sols[start][end]
	score = 0
	if total % 2 != 0:
		sols[start][end] = 0
		return 0
	if end - start == 2:
		if array[start] == array[end - 1]:
			sols[start][end] = 1
			return 1
		else:
			sols[start][end] = 0
			return 0
	if end - start == 1:
		sols[start][end] = 0
		return 0
	leftsum = 0
	rightsum = total
	for i in range(start, end - 1):
		leftsum += array[i]
		rightsum -= array[i]
		if leftsum > rightsum:
			break
		if leftsum == rightsum:
			assert len(array[start:i + 1]) < len(array[start:end])
			score = max(score, 1 + partion(array, start, i + 1, leftsum), 1 + partion(array, i + 1, end, rightsum))
	sols[start][end] = score
	return score
cases = int(input())
for case in range(cases):
	length = int(input())
	array = [int(x) for x in input().split(' ')]
	sols = {i: {} for i in range(length)}
	t = sum(array)
	if t > 0:
		array = [i for i in array if i > 0]
	score = partion(array, 0, len(array), sum(array))
	print(score)


T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(val) for val in input().split(' ')]

	def checkStuff(v, score=0):
		s = sum(v)
		if s % 2 != 0:
			return score
		if s == 0:
			return score + len(v) - 1
		target = int(s / 2)
		tempSum = 0
		for i in range(len(v)):
			tempSum += v[i]
			if tempSum == target:
				return max(checkStuff(v[i + 1:], score + 1), checkStuff(v[:i + 1], score + 1))
			if tempSum > target:
				return score
		return score
	score = checkStuff(arr)
	print(score)


def rec_nikita(list):
	total = sum(list)
	if total == 0:
		return max(0, len(list) - 1)
	if 1 == len(list) or total % 2 != 0:
		return 0
	else:
		target = total / 2
		cumul = 0
		split_index = 0
		for (count, item) in enumerate(list):
			cumul += item
			if cumul >= target:
				split_index = count
				break
		if cumul != target:
			return 0
		else:
			return 1 + max(rec_nikita(list[split_index + 1:]), rec_nikita(list[:split_index + 1]))
n = int(input().strip())
for _ in range(0, n):
	count_value = int(input().strip())
	test_array = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	print(rec_nikita(test_array))


def getMaxScore(A, s):
	s = s // 2
	lenA = len(A)
	if s == 0:
		if A == [0 for i in range(lenA)]:
			return lenA - 1
		else:
			return 0
	if lenA == 0:
		return 0
	sumA = 0
	i = 0
	while not sumA >= s:
		sumA += A[i]
		i += 1
	if sumA > s:
		return 0
	else:
		left = A[:i]
		right = A[i:]
		return 1 + max(getMaxScore(left, sum(left)), getMaxScore(right, sum(right)))
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	score = getMaxScore(A, sum(A))
	print(score)


def max_points(a, sum):
	if len(a) == 1:
		return 0
	(left_sum, right_sum) = (0, sum)
	if right_sum == 0:
		return len(a) - 1
	for (i, ai) in enumerate(a):
		left_sum += ai
		right_sum -= ai
		if left_sum > right_sum:
			return 0
		if left_sum == right_sum:
			middle = i + 1
			return 1 + max(max_points(a[:middle], left_sum), max_points(a[middle:], left_sum))
	return 0
tests = int(input())
for test in range(tests):
	input()
	a = [int(c) for c in input().split(' ')]
	print(max_points(a, sum(a)))


import sys
cache = {}

def array_sum(a):
	return sum(a)

def array_split(a):
	if a in cache:
		return cache[a]
	if sum(a) == 0:
		return len(a) - 1
	if len(a) < 2:
		cache[a] = 0
		return cache[a]
	i = find_split(a)
	if i:
		cache[a] = 1 + max(array_split(a[:i]), array_split(a[i:]))
		return cache[a]
	else:
		cache[a] = 0
		return cache[a]

def find_split(a, i=None, j=None):
	if not i and (not j):
		(i, j) = (1, len(a) - 1)
	if i == j:
		mid = i
	else:
		mid = i + (j - i) // 2
	(x, y) = (array_sum(a[:mid]), array_sum(a[mid:]))
	if x == y:
		return mid
	elif j - i <= 2:
		if array_sum(a[:i]) == array_sum(a[i:]):
			return i
		if array_sum(a[:j]) == array_sum(a[j:]):
			return j
		return None
	elif x < y:
		return find_split(a, mid, j)
	else:
		return find_split(a, i, mid)
T = int(sys.stdin.readline().strip())
for _ in range(T):
	sys.stdin.readline()
	A = tuple((int(x) for x in sys.stdin.readline().split()))
	print(array_split(A))


def getEqualIndex(array):
	left = 0
	right = sum(array)
	i = 0
	for value in array:
		left += value
		right -= value
		if left == right:
			return i
		i += 1
	return -1

def getMaxPoints(array):
	if len(array) <= 1:
		return 0
	equalIndex = getEqualIndex(array)
	if equalIndex == -1:
		return 0
	elif equalIndex == 0 and array.count(array[0]) == len(array):
		return len(array) - 1
	else:
		return 1 + max(getMaxPoints(array[:equalIndex + 1]), getMaxPoints(array[equalIndex + 1:]))
cases = int(input())
for i in range(cases):
	size = int(input())
	array = []
	for value in input().strip().split(' '):
		array += [int(value)]
	print(getMaxPoints(array))


def partition(a):
	(left, right) = ([], [])
	sum_a = sum(a)
	if sum_a == 0:
		return (len(a) - 1, right, True)
	if sum_a % 2 != 0:
		return (left, right, False)
	curr_sum = 0
	for i in range(len(a)):
		x = a[i]
		curr_sum += x
		sum_a -= x
		left.append(x)
		if curr_sum < sum_a:
			continue
		elif curr_sum == sum_a:
			return (left, a[i + 1:], True)
		else:
			return ([], [], False)

def max_points(a):
	(left_a, right_a, part_poss) = partition(a)
	if type(left_a) == int:
		return left_a
	elif not part_poss:
		return 0
	else:
		return max(max_points(left_a), max_points(right_a)) + 1
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(max_points(A))


def getIndexOf(array, element):
	for (i, x) in enumerate(array):
		if x == element:
			return i
	return -1

def countMoves(array, length):
	if length == 1:
		return 0
	sumarr = [0] * length
	i = 0
	currsum = 0
	allZero = True
	for x in array:
		if x != 0:
			allZero = False
		sumarr[i] = currsum + x
		currsum = sumarr[i]
		i += 1
	if allZero is True:
		return length - 1
	last = sumarr[-1]
	halfIndex = getIndexOf(sumarr, int(last / 2))
	if last % 2 == 0 and halfIndex != -1:
		leftMaxCount = countMoves(array[:halfIndex + 1], halfIndex + 1)
		rightMaxCount = countMoves(array[halfIndex + 1:], length - (halfIndex + 1))
		return 1 + max(leftMaxCount, rightMaxCount)
	else:
		return 0
tests = int(input())
for _ in range(0, tests):
	length = int(input())
	array = [int(x) for x in input().split(' ')]
	print(countMoves(array, length))


def find_max_score(array):
	unprocessed = [(0, array), (0, array)]
	scores = [0]
	while len(unprocessed) > 0:
		(score, subarray) = unprocessed.pop()
		if len(subarray) < 2:
			scores.append(score)
			continue
		total = sum(subarray)
		current_total = 0
		for (idx, num) in enumerate(subarray):
			current_total += num
			if total - current_total == current_total:
				unprocessed.append((score + 1, subarray[:idx + 1]))
				unprocessed.append((score + 1, subarray[idx + 1:]))
				break
		if current_total == total:
			scores.append(score)
	return max(scores)
T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	array = [int(i) for i in input().strip().split(' ')]
	print(find_max_score(array))


def nktg(arr, start, end):
	if start >= end:
		return 0
	arr_sum = sum(arr[start:end])
	if arr_sum == 0:
		return end - start - 1
	left = 0
	key = '{0},{1}'.format(start, end)
	mid = -1
	if not count.get(key):
		for i in range(start, end - 1):
			left += arr[i]
			if left == arr_sum / 2:
				mid = i + 1
				break
		if mid != -1:
			count[key] = max(nktg(arr, start, mid), nktg(arr, mid, end)) + 1
		else:
			return 0
	return count[key]
t = int(input().strip())
for _ in range(t):
	count = {}
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	ans = nktg(arr, 0, n)
	print(ans)


__author__ = 'shoaib'
import sys
import math
sys.setrecursionlimit(150000)

def ScoreOndiv(arr, n, l):
	if n - l == 2 and arr[n - 1] == arr[l]:
		return 1
	if n - l == 2:
		return 0
	if n - l == 1:
		return 0
	p = 0
	for x in range(l, n):
		p += a[x]
	if p == 0 and math.log(n, 2) // 1 == math.log(n, 2):
		return n - 1
	if p % 2 != 0:
		return 0
	p = p / 2
	q = 0
	for x in range(l, n):
		q += a[x]
		if q == p:
			return 1 + max(ScoreOndiv(arr, x + 1, l), ScoreOndiv(arr, n, x + 1))
	return 0
t = int(sys.stdin.readline())
while t > 0:
	n = int(sys.stdin.readline())
	a = sys.stdin.readline()
	a = a.split(' ')
	for x in range(n):
		a[x] = int(a[x])
	print(ScoreOndiv(a, n=n, l=0))
	t -= 1


def nikita(l):
	s = sum(l)
	if s % 2 != 0 or len(l) == 1:
		return 0
	c = 0
	for i in range(len(l) - 1):
		c += l[i]
		if c == int(s / 2):
			m = l[:i + 1]
			n = l[i + 1:]
			return 1 + max(nikita(m), nikita(n))
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if a == [0] * n:
		print(n - 1)
	else:
		print(nikita(a))


def nikita(l):
	s = sum(l)
	if s % 2 != 0 or len(l) == 1:
		return 0
	c = 0
	for i in range(len(l) - 1):
		c += l[i]
		if c == int(s / 2):
			return 1 + max(nikita(l[:i + 1]), nikita(l[i + 1:]))
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	if a == [0] * n:
		print(n - 1)
	else:
		print(nikita(a))


import bisect

def dep(nums, start, end):
	(sum, temp) = (0, 0)
	if end <= start:
		return 0
	sum = nums[end] - nums[start - 1]
	if sum % 2 == 1:
		return 0
	if sum == 0:
		return end - start
	mid = sum / 2 + nums[start - 1]
	left = bisect.bisect_left(nums, mid, start, end + 1)
	if nums[left] != mid:
		return 0
	return 1 + max(dep(nums, start, left), dep(nums, left + 1, end))
for _ in range(int(input().strip())):
	n = int(input().strip())
	nums = list(map(int, input().split(' ')))
	data = [0] * (len(nums) + 1)
	for i in range(1, len(nums) + 1):
		data[i] = data[i - 1] + nums[i - 1]
	print(dep(data, 1, len(nums)))


def game(arr, s, e):
	global summ
	if s == e:
		return 0
	k = s
	while k < e:
		if summ[k + 1] - summ[s] == summ[e + 1] - summ[k + 1]:
			break
		k += 1
	if k < e:
		return 1 + max(game(arr, s, k), game(arr, k + 1, e))
	return 0
import sys
sys.setrecursionlimit(100000)
t = int(input())
global summ
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	summ = [0]
	summ.extend(arr[:])
	for j in range(1, n + 1):
		summ[j] += summ[j - 1]
	print(game(arr, 0, n - 1))


class Node:

	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

class Tree:

	def __init__(self, root):
		self.root = root

	def max_height(self, node, count=0):
		if node is None:
			return count
		left = self.max_height(node.left, count + 1)
		right = self.max_height(node.right, count + 1)
		return max(left, right)

def solution(arr, n):
	acc = [0]
	for i in range(1, n + 1):
		acc.append(acc[i - 1] + arr[i - 1])
	if acc[-1] % 2 == 1:
		return 0
	if sum(acc) == 0 and sum(arr) == 0:
		return n - 1
	left = 1
	right = n
	value = acc[-1] // 2
	root = make_tree(acc, left, right, value)
	if root is None:
		return 0
	return Tree(root).max_height(root)

def make_tree(acc, left, right, value):
	root_val = find_half(acc, left, right, value)
	if root_val == -1:
		return None
	root = Node(root_val)
	if value % 2 == 0:
		value //= 2
		root.left = make_tree(acc, left, root_val - 1, value)
		root.right = make_tree(acc, root_val + 1, right, value)
	return root

def find_half(acc, left, right, value):
	search_val = acc[left - 1] + value
	while left <= right:
		mid = (left + right) // 2
		if acc[mid] == search_val:
			return mid
		elif acc[mid] < search_val:
			left = mid + 1
		else:
			right = mid - 1
	return -1

def build_arr():
	str_arr = input().split(' ')
	return [int(num) for num in str_arr]
t = int(input())
for i in range(t):
	n = int(input())
	arr = build_arr()
	print(solution(arr, n))


from itertools import accumulate
from bisect import bisect_left

def playGame(cum, i, j):
	if j - i < 2:
		return 0
	s = cum[j - 1] - cum[i - 1]
	if s & 1:
		return 0
	if s == 0:
		return j - i - 1
	dest = (s >> 1) + cum[i - 1]
	k = bisect_left(cum, dest, i, j)
	if cum[k] != dest:
		return 0
	return 1 + max(playGame(cum, i, k + 1), playGame(cum, k + 1, j))
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	cum = [0] + list(accumulate(A))
	print(playGame(cum, 1, N + 1))


def getScore(array):
	if len(array) == 0:
		return 0
	s = sum(array)
	if s == 0:
		return len(array) - 1
	if s % 2 == 1:
		return 0
	else:
		s /= 2
	k = 0
	i = 0
	while k < s:
		k += array[i]
		i += 1
	if k == s:
		return max(getScore(array[0:i]), getScore(array[i:len(array)])) + 1
	else:
		return 0
t = int(input())
for i in range(0, t):
	n = int(input())
	array = list(map(int, input().split()))
	print(getScore(array))


def solve(nums):
	sum_total = sum(nums)
	if sum_total == 0:
		return len(nums) - 1
	sum_current = 0
	for (i, num) in enumerate(nums):
		sum_current += num
		if sum_current == sum_total / 2:
			if len(nums) <= i + 1:
				return 0
			return 1 + max(solve(nums[:i + 1]), solve(nums[i + 1:]))
		if sum_current > sum_total / 2:
			break
	return 0
cases = int(input())
for case in range(cases):
	input()
	data = list(map(int, input().split(' ')))
	print(str(solve(data)))


def solve_game(arr):
	s = sum(arr)
	if s % 2 != 0:
		return 0
	c = 0
	i = 0
	all_zeros = s == 0
	for a in arr:
		c += a
		i += 1
		if all_zeros and a != 0:
			all_zeros = False
		if c >= s // 2:
			break
	if all_zeros:
		return len(arr) - 1
	if c != s // 2:
		return 0
	left = solve_game(arr[0:i])
	right = solve_game(arr[i:])
	return 1 + max(left, right)
for _ in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split(' ')]
	print(solve_game(A))


import sys

def count(array, a, b, sumarray):
	if a == b:
		return 0
	ispart = exists(array, a, b, sumarray)
	if ispart != -1:
		maxpart = max(count(array, a, ispart, sumarray / 2), count(array, ispart + 1, b, sumarray / 2))
		return maxpart + 1
	else:
		return 0

def exists(array, a, b, sumarray):
	if sumarray % 2 == 1:
		return -1
	else:
		length = int(b - a + 1)
		c_sum = [0] * len(array)
		c_sum[a] = array[a]
		if c_sum[a] == sumarray / 2:
			return a
		for i in range(1, length):
			c_sum[a + i] = c_sum[a + i - 1] + array[a + i]
			if c_sum[a + i] == sumarray / 2:
				return a + i
		return -1
k = int(input())
for i in range(k):
	n = int(input())
	line = str(input())
	numbers = []
	numbers = line.split()
	for i in range(len(numbers)):
		numbers[i] = int(numbers[i])
	if sum(numbers) == 0:
		total = n - 1
	else:
		total = count(numbers, 0, n - 1, sum(numbers))
	print(total)


from bisect import bisect_left as bisect

def arrayGame(n, arr):
	presum = [0, arr[0]]
	for i in range(1, n):
		presum.append(arr[i] + presum[-1])
	if presum[-1] == 0:
		return n - 1

	def divide(i, j):
		if j - i <= 1:
			return 0
		s = presum[j] - presum[i]
		half = s / float(2) + presum[i]
		d = bisect(presum, half, lo=i, hi=j - 1)
		if presum[d] != half:
			return 0
		return 1 + max(divide(i, d), divide(d, j))
	return divide(0, n)
nc = int(input())
while nc:
	nc -= 1
	print(arrayGame(int(input()), [int(x) for x in input().split(' ')]))


import bisect

def dep(nums, start, end):
	(sum, temp) = (0, 0)
	if end <= start:
		return 0
	sum = nums[end] - nums[start - 1]
	if sum % 2 == 1:
		return 0
	if sum == 0:
		return end - start
	mid = sum / 2 + nums[start - 1]
	left = bisect.bisect_left(nums, mid, start, end + 1)
	if nums[left] != mid:
		return 0
	return 1 + max(dep(nums, start, left), dep(nums, left + 1, end))
for _ in range(int(input().strip())):
	n = int(input().strip())
	nums = list(map(int, input().split(' ')))
	data = [0] * (len(nums) + 1)
	for i in range(1, len(nums) + 1):
		data[i] = data[i - 1] + nums[i - 1]
	print(dep(data, 1, len(nums)))


import bisect

def dep(nums, start, end):
	(sum, temp) = (0, 0)
	if end <= start:
		return 0
	sum = nums[end] - nums[start - 1]
	if sum % 2 == 1:
		return 0
	if sum == 0:
		return end - start
	mid = sum / 2 + nums[start - 1]
	left = bisect.bisect_left(nums, mid, start, end + 1)
	if nums[left] != mid:
		return 0
	return 1 + max(dep(nums, start, left), dep(nums, left + 1, end))
for _ in range(int(input().strip())):
	n = int(input().strip())
	nums = list(map(int, input().split(' ')))
	data = [0] * (len(nums) + 1)
	for i in range(1, len(nums) + 1):
		data[i] = data[i - 1] + nums[i - 1]
	print(dep(data, 1, len(nums)))


def finder(arr):
	s = sum(arr)
	if s == 0:
		return len(arr) - 1
	L = 0
	R = s
	for i in range(1, len(arr)):
		L += arr[i - 1]
		R -= arr[i - 1]
		if L == R:
			return 1 + max(finder(arr[:i]), finder(arr[i:]))
	return 0
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(finder(arr))


t = int(input())

def dp(p):
	if len(p) < 2:
		return 0
	a = [x for x in p if x > 0]
	if len(a) == 0:
		return len(p) - 1
	t = [0] * len(a)
	t[0] = a[0]
	for i in range(1, len(a)):
		t[i] = t[i - 1] + a[i]
	if t[-1] % 2 == 1:
		return 0
	else:
		s = t[-1] / 2
		if s not in t:
			return 0
		else:
			i = t.index(s)
			return 1 + max(dp(a[:i + 1]), dp(a[i + 1:]))
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().strip().split()]
	print(dp(a))


def is_div(a):
	total = sum(a)
	if total % 2 != 0:
		return -1
	i = 0
	temp = 0
	found = 0
	while i < len(a) and temp <= total / 2:
		temp = temp + a[i]
		if temp == total / 2:
			found = 1
			break
		i = i + 1
	if found:
		return i
	else:
		return -1

def find_cost(a):
	if sum(a) == 0:
		return len(a) - 1
	else:
		cut_i = is_div(a)
		if cut_i == -1:
			return 0
		else:
			return 1 + max(find_cost(a[:cut_i + 1]), find_cost(a[cut_i + 1:]))
test_case = int(input())
for test in range(test_case):
	a_len = int(input())
	a = [int(i) for i in input().split()]
	print(find_cost(a))


import sys

class Node:

	def __init__(self):
		self.left = None
		self.right = None
		self.data = None
		self.depth = None

def successive_add(sequence, n):
	sum_seq = []
	sum = 0
	for i in range(n):
		sum += sequence[i]
		sum_seq += [sum]
	return sum_seq

def nikita_and_game(sequence, n):
	tuples = []
	tree = Node()
	successive_sum = successive_add(sequence, n)
	tree.data = (0, n - 1)
	tree.depth = 0
	tuples += [tree]
	height = 0
	while len(tuples) > 0:
		node = tuples.pop(0)
		lo = node.data[0]
		hi = node.data[1]
		if lo == hi:
			continue
		k = lo
		sum_lo_hi = successive_sum[hi] - successive_sum[lo] + sequence[lo]
		sum = 0
		while k < hi:
			sum += sequence[k]
			if sum_lo_hi - sum == sum:
				left = Node()
				left.data = (lo, k)
				left.depth = node.depth + 1
				right = Node()
				right.data = (k + 1, hi)
				right.depth = node.depth + 1
				node.left = left
				node.right = right
				tuples += [node.left, node.right]
				height = max(left.depth, right.depth)
				break
			else:
				k += 1
	return height
tests = int(sys.stdin.readline())
for i in range(tests):
	n = int(sys.stdin.readline())
	sequence = [int(x) for x in sys.stdin.readline().split(' ')]
	count = nikita_and_game(sequence, n)
	print(count)


def numSplits(arr):
	arrSum = sum(arr)
	if arrSum == 0:
		return len(arr) - 1
	if arrSum % 2 == 1:
		return 0
	halfSum = 0
	for i in range(len(arr)):
		halfSum = halfSum + arr[i]
		if halfSum == arrSum / 2:
			return 1 + max(numSplits(arr[:i + 1]), numSplits(arr[i + 1:]))
	return 0
tests = int(input())
for i in range(tests):
	input()
	arr = [int(x) for x in input().strip().split()]
	print(numSplits(arr))


def num_split(array, array_sum):
	if len(array) == 1:
		return 0
	running_sum = 0
	for x in range(len(array) - 1):
		running_sum += array[x]
		right_sum = array_sum - running_sum
		if running_sum == right_sum:
			return 1 + max(num_split(array[0:x + 1], running_sum), num_split(array[x + 1:], running_sum))
	return 0
num_trials = int(input())
for trial in range(num_trials):
	input()
	array = [int(a) for a in input().split()]
	zeros = True
	for x in array:
		if x != 0:
			zeros = False
	if not zeros:
		print(num_split(array, sum(array)))
	else:
		print(len(array) - 1)


import sys

def game(A, suma, index):
	if len(A) <= 1:
		return 0
	partialSum = 0
	i = 0
	while partialSum != suma:
		if i < len(A):
			partialSum += A[i]
			if partialSum == sum:
				break
			else:
				i += 1
		else:
			return 0
	if suma % 2 != 0:
		return 1
	else:
		v = 1 + game(A[0:i], int(sum(A[0:i]) / 2), index)
		v2 = 1 + game(A[i:], int(sum(A[i:]) / 2), i)
		return max(v, v2)
cases = int(input().strip())
for c in range(cases):
	Asize = int(input().strip())
	A = [int(x) for x in input().strip().split(' ')]
	if sum(A) == 0:
		print(len(A) - 1)
	elif sum(A) % 2 != 0:
		print(0)
	else:
		print(game(A, int(sum(A) / 2), 0))


numsets = int(input())

def findMaxMoves(ele, sum):
	sum = sum / 2
	if sum == 0:
		if ele != [0 for x in range(0, len(ele))]:
			return 0
		else:
			return len(ele) - 1
	s = 0
	i = 0
	n = len(ele)
	if len(ele) == 1 or len(ele) == 0:
		return 0
	while s != sum and i < n:
		s += ele[i]
		i += 1
	if i >= n:
		return 0
	return 1 + max(findMaxMoves(ele[0:i], sum), findMaxMoves(ele[i:n], sum))

def findMaxDeepness(array, amin, amax):
	if (amin + amax) % 2 == 0 and (amin + amax) / 2 in array:
		return 1 + max(findMaxDeepness(array, amin, (amin + amax) / 2), findMaxDeepness(array, (amin + amax) / 2, amax))
	return 0
for i in range(numsets):
	els = int(input())
	values = [int(x) for x in input().split(' ')]
	print(findMaxMoves(values, sum(values)))


from math import log
from bisect import bisect_left

def dfs(n, a_sum):
	total = a_sum[-1]
	if total == 0:
		return n - 1
	for i in range(1, int(log(total, 2)) + 2):
		if total % 2 ** i != 0:
			max_depth = i - 1
	stack = [(0, total, 0)]
	best_depth = 0
	while stack:
		(lower, upper, depth) = stack.pop()
		mid = (upper + lower) // 2
		i = bisect_left(a_sum, mid)
		if i != n and a_sum[i] == mid:
			if depth + 1 == max_depth:
				return max_depth
			if depth + 1 > best_depth:
				best_depth = depth + 1
			stack.append((mid, upper, depth + 1))
			stack.append((lower, mid, depth + 1))
	return best_depth
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a_sum = [a[0]]
	for x in range(1, n):
		a_sum.append(a_sum[x - 1] + a[x])
	depth = dfs(n, a_sum)
	print(depth)