For an array A of length N, let F(A) denote the sum of the product of all the subarrays of A. Formally,

F(A) = \sum_{L=1}^N \sum_{R=L}^N  (\prod_{i=L}^R A_{i}\right )

For example, let A = [1, 0, 1], then there are 6 possible subarrays:

Subarray [1, 1] has product = 1
Subarray [1, 2] has product = 0
Subarray [1, 3] has product = 0
Subarray [2, 2] has product = 0
Subarray [2, 3] has product = 0
Subarray [3, 3] has product = 1

So F(A) = 1+1 = 2.
  
Given a binary array A, determine the value of F(A).

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N denoting the length of the array.
- The second line contains N space-separated integers denoting the array A.

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

For each test case, output on a new line the value of F(A).

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 1$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

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

----- Sample Output 1 ------ 
2
0
3
4

----- explanation 1 ------ 
Test case $1$: Explained in the statement.

Test case $2$: There is only $1$ subarray and it has product $= 0$.

Test case $3$: All the $3$ subarrays have product $= 1$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
t = int(input())
for ni in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	(k, s) = (0, 0)
	for i in range(n):
		if a[i] == 1:
			s = s + k + 1
			k = k + 1
		else:
			k = 0
	print(s)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	suma = 0
	k = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			suma += k + 1
			k = k + 1
		else:
			k = 0
	print(suma)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()] + [0]
	(ans, cur) = (0, 0)
	for i in a:
		if i:
			cur += 1
		else:
			ans += cur * (cur + 1) // 2
			cur = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(c, s) = (0, 0)
	l = []
	for i in range(n):
		if a[i] == 1:
			c += 1
		else:
			l.append(c)
			c = 0
	l.append(c)
	for i in l:
		s += i * (i + 1) // 2
	print(s)


for i in range(int(input())):
	n = input()
	a = list(map(int, input().split()))
	sums = a.count(1)
	c = 0
	for i in range(len(a)):
		if a[i] == 1:
			c += 1
		if a[i] == 0 or i == len(a) - 1:
			sums += c * (c - 1) // 2
			c = 0
	print(sums)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(x, y) = (0, 0)
	for i in range(n):
		if l[i] == 1:
			x += y + 1
			y += 1
		else:
			y = 0
	print(x)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(x, y) = (0, 0)
	for i in range(n):
		if a[i] == 1:
			x += y + 1
			y += 1
		else:
			y = 0
	print(x)


for _ in range(int(input())):
	N = int(input())
	in_str = list(input().split())
	score = 0
	cnt = 0
	i = 0
	while i < N:
		if in_str[i] == '0':
			i += 1
			continue
		while i < N and in_str[i] == '1':
			cnt += 1
			i += 1
		score += int(cnt * (cnt + 1) / 2)
		cnt = 0
	print(score)


a = int(input())
for i in range(a):
	x = int(input())
	T = [int(x) for x in input().split()]
	k = list(T)
	c = 0
	h = 0
	for j in range(0, len(k)):
		if k[j] == 1:
			c += h + 1
			h = h + 1
		else:
			h = 0
	print(c)


T = int(input())
for i in range(0, T):
	n = int(input())
	l = list(map(int, input().split()))
	w = 0
	sm = 0
	while w < len(l):
		if l[w] == 0:
			w += 1
		else:
			count = 0
			j = w
			while j < len(l):
				if l[j] == 1:
					count += 1
					j += 1
				else:
					w = j + 1
					j = len(l) + 1
			sm += count * (count + 1) // 2
			if j == len(l):
				w = len(l)
	print(sm)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	k = 0
	for i in range(n):
		if a[i] == 1:
			sum += k + 1
			k = k + 1
		else:
			k = 0
	print(sum)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	sum = 0
	k = 0
	for i in range(n):
		if a[i] == 1:
			sum += k + 1
			k = k + 1
		else:
			k = 0
	print(sum)


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	ans = 0
	cur = 0
	for i in x:
		cur += i
		if i:
			ans += cur
		else:
			cur = 0
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(cnt, ans) = (0, 0)
	for i in range(n):
		if 1 == l[i]:
			cnt = cnt + 1
		else:
			ans = ans + cnt * (cnt + 1) // 2
			cnt = 0
	ans = ans + cnt * (cnt + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	r = 0
	for i in a:
		if i == 1:
			r += 1
		else:
			ans += r * (r + 1) // 2
			r = 0
	ans += r * (r + 1) // 2
	print(ans)


t = int(input())
for _ in range(0, t):
	n = int(input())
	x = list(map(int, input().split()))
	(j, s) = (0, 0)
	for i in x:
		if i == 1:
			j += 1
		else:
			s = s + j * (j + 1) // 2
			j = 0
	s = s + j * (j + 1) // 2
	print(s)


T = int(input())
for case in range(T):
	n = int(input())
	a = input().replace(' ', '')
	a = list(a.split('0'))
	ans = 0
	for i in a:
		k = len(i)
		ans += k * (k + 1) // 2
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	s = 0
	c = 0
	l = list(map(int, input().split()))
	for j in l:
		if j == 1:
			c += 1
			s += c
		else:
			c = 0
	print(s)


for _ in range(int(input())):
	n = int(input())
	s = 0
	contiguous = 0
	for i in map(int, input().split()):
		if i == 1:
			contiguous += 1
			s += contiguous
		else:
			contiguous = 0
	print(s)


for _ in range(int(input())):
	m = int(input())
	ary = list(map(int, input().split()))[:m]
	answer = 0
	r = 0
	for i in range(m):
		if ary[i] == 1:
			r += 1
		else:
			answer += r * (r + 1) // 2
			r = 0
	answer += r * (r + 1) // 2
	print(answer)


T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	S = 0
	zeros = []
	lens = []
	for i in range(N):
		if L[i] == 0:
			zeros.append(i)
	zeros = [-1] + zeros + [N]
	for i in range(1, len(zeros)):
		lens.append(zeros[i] - zeros[i - 1] - 1)
	for i in lens:
		S += i * (i + 1) // 2
	print(S)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = []
	c = 0
	for i in l:
		if i == 1:
			c += 1
			f = 0
		else:
			f = 1
			m.append(c)
			c = 0
	if f == 0:
		m.append(c)
	ans = 0
	for i in m:
		ans += i * (i + 1) // 2
	print(ans)


from functools import reduce
for test in range(int(input())):
	size = int(input())
	arr = list(map(int, input().split()))
	res = 0
	count = 1
	tmp = 1
	for item in arr:
		if item == 0:
			res += tmp - count
			count = 1
			tmp = 1
			continue
		else:
			count += 1
			tmp += count
	if item != 0:
		res += tmp - count
	print(res)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ones = 0
	ans = 0
	for j in range(length):
		if arr[j] == 1:
			ones += 1
		if arr[j] == 0 or j == length - 1:
			ans += ones * (ones + 1) // 2
			ones = 0
	print(ans)


import sys
input = sys.stdin.readline
M = 1000000007

def solve():
	n = int(input())
	li = list(map(int, input().split()))
	s = 0
	t = 0
	for i in range(n):
		if li[i] == 1:
			t += 1
		else:
			t = 0
		s += t
	print(s)
for _ in range(int(input())):
	solve()


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().rstrip().split()))
	product = [0] * n
	arr_sum = arr[0]
	product_sum = 0
	if n > 2:
		for ele in range(1, n):
			if arr[ele] * arr[ele - 1]:
				product[ele] += product[ele - 1] + 1
				product_sum += product[ele]
			arr_sum += arr[ele]
		print(product_sum + arr_sum)
	elif n == 2:
		print(arr[0] * arr[1] + sum(arr))
	elif n == 1:
		print(arr[0])


t = int(input())
for test in range(t):
	n = int(input())
	arr = list([int(x) for x in input().split()])
	answer = int(0)
	length = int(0)
	for i in range(n):
		if arr[i] == 1:
			length += 1
		else:
			answer += length * (length + 1) / 2
			length = 0
	answer += length * (length + 1) / 2
	print(int(answer))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	res = 0
	c = 0
	for i in range(n):
		if arr[i] == 0:
			c = 0
		else:
			c += 1
		res += c
	print(res)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().strip().split()))
	ans = 0
	group = 0
	for i in range(N):
		if A[i]:
			group += 1
		else:
			ans += group * (group + 1) // 2
			group = 0
	else:
		ans += group * (group + 1) // 2
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	count = 0
	index = 0
	while index < n:
		if a[index] == 1:
			ct = 0
			while index < n and a[index] == 1:
				ct += 1
				index += 1
			count += ct * (ct + 1) // 2
		else:
			index += 1
	print(count)


T = int(input())
for _ in range(T):
	n = int(input())
	arr = map(int, input().split(' '))
	ans = []
	count = 0
	for a in arr:
		if a != 0:
			count += 1
		else:
			ans.append(count)
			count = 0
	ans.append(count)
	for i in range(len(ans)):
		ans[i] = ans[i] * (ans[i] + 1) // 2
	print(sum(ans))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	(cnt, res) = (0, 0)
	for i in range(n):
		if a[i] == 1:
			cnt += 1
		else:
			res += cnt * (cnt + 1) // 2
			cnt = 0
	res += cnt * (cnt + 1) // 2
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))[:n]
	s = 0
	r = 0
	for i in range(n):
		if arr[i] == 0:
			s = 0
		else:
			s += 1
		r += s
	print(r)


t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))[:n]
	s = 0
	r = 0
	for i in range(len(a)):
		if a[i] == 0:
			s = 0
		else:
			s += 1
		r += s
	print(r)
	t -= 1


for tc in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	x = 1
	c = 0
	s = 0
	for i in range(n):
		if x == p[i] and i != n - 1:
			c += 1
		else:
			if i == n - 1 and p[i] == 1:
				c += 1
			s = s + int(c * (c + 1) / 2)
			x = 1
			c = 0
	print(s)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prev = 1
	c = 0
	summ = 0
	for i in range(n):
		if prev == a[i] and i != n - 1:
			prev = a[i]
			c = c + 1
		else:
			if i == n - 1 and a[i] == 1:
				c = c + 1
			summ = summ + int(c * (c + 1) / 2)
			prev = 1
			c = 0
	print(summ)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	(sum1, cnt) = (0, 0)
	for i in range(n):
		if arr[i] == 1:
			cnt += 1
		else:
			sum1 = sum1 + cnt * (cnt + 1) // 2
			cnt = 0
	sum1 += cnt * (cnt + 1) // 2
	print(sum1)


def checking(n, li):
	bi = []
	s = 0
	num = 0
	c = 0
	k = 0
	for i in range(0, n):
		if li[i] == 1:
			c += 1
		else:
			bi.append(c)
			c = 0
	bi.append(c)
	if len(bi) == 0:
		return 0
	else:
		for b in bi:
			num = b * (b + 1) // 2
			s += num
	return s
t = int(input())
for i in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	val = checking(n, li)
	print(val)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	res = []
	c = 0
	for i in range(n):
		if a[i] == 0:
			if c != 0:
				res.append(c)
			c = 0
		else:
			c += 1
	res.append(c)
	ans = 0
	for el in res:
		ans += el * (el + 1) // 2
	print(ans)
	t -= 1


def compute(arr):
	arr_sum = 0
	prod = 0
	for i in arr:
		if i == 1:
			prod = prod + 1
		else:
			arr_sum += int((prod + 1) * prod / 2)
			prod = 0
	if prod != 0:
		arr_sum += int((prod + 1) * prod / 2)
	print(arr_sum)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	compute(arr)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	total = 0
	i = 1
	cnt1 = 0 if A[0] == 0 else 1
	while i < n:
		if A[i] == 1:
			cnt1 += 1
		elif A[i] == 0 and A[i - 1] == 1:
			total += cnt1 * (cnt1 + 1) // 2
			cnt1 = 0
		i += 1
	if cnt1 != 0:
		total += cnt1 * (cnt1 + 1) // 2
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	Arr = list(map(int, input().split()))
	sumArr = 0
	prod = 0
	for i in Arr:
		if i == 1:
			prod = prod + 1
		else:
			sumArr += (prod + 1) * prod / 2
			prod = 0
	if prod != 0:
		sumArr += (prod + 1) * prod / 2
	print(int(sumArr))


n = int(input())
for _ in range(n):
	alen = int(input())
	a = list(map(int, input().split(' ')))
	suma = 0
	counter = 0
	for i in a:
		if i == 1:
			counter += 1
		else:
			suma += counter * (counter + 1) / 2
			counter = 0
	if counter != 0:
		suma += counter * (counter + 1) / 2
	print(int(suma))


for _ in range(int(input())):
	ans = 0
	n = int(input())
	arr = input().split(' 0 ')
	for item in arr:
		item = [int(x) for x in item.split()]
		try:
			for i in range(len(item)):
				item.remove(0)
		except Exception as nozero:
			pass
		lenofitem = len(item)
		ans += lenofitem * (lenofitem + 1) / 2
	print(int(ans))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(ans, cnt) = (0, 0)
	for i in range(n):
		if arr[i] == 1:
			cnt += 1
		else:
			ans += cnt * (cnt + 1) // 2
			cnt = 0
	ans += cnt * (cnt + 1) // 2
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	c = 0
	ans = 0
	for i in range(n):
		if s[i] == 1:
			c += 1
		else:
			ans += c * (c + 1) // 2
			c = 0
	ans += c * (c + 1) // 2
	print(ans)


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	(c, ans) = (0, 0)
	for i in l:
		if i == 1:
			c = c + 1
		else:
			ans += c * (c + 1) // 2
			c = 0
	ans += c * (c + 1) // 2
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	arr = ''.join([x for x in input().split()])
	arr = arr.split('0')
	(s, l) = (0, 0)
	for i in arr:
		l = len(i)
		s += l * (l + 1) / 2
	print(int(s))


import math
for _ in range(int(input())):
	n = int(input())
	arr = input().split()
	arr.append('0')
	(s, l) = (0, 0)
	for i in arr:
		if i == '0':
			s += l * (l + 1) / 2
			l = 0
		else:
			l += 1
	print(int(s))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	s = 0
	i = 0
	while i < n:
		c = 0
		if l[i] == 0:
			i = i + 1
			continue
		if l[i] == 1:
			j = i
			while j < n and l[j] == 1:
				c = c + 1
				j = j + 1
			s = s + c * (c + 1) / 2
			s = int(s)
			i = i + c
	print(s)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(c, a) = (0, 0)
	for j in range(N):
		if A[j] == 1:
			c = c + 1
		else:
			a = a + c * (c + 1) // 2
			c = 0
	a = a + c * (c + 1) // 2
	print(a)


T = int(input())
for i in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	s = 0
	b = 0
	for i in a:
		if i == 1:
			s = s + 1
		else:
			b += s * (s + 1) // 2
			s = 0
	b += s * (s + 1) // 2
	print(b)


t = int(input())

def mul(arr):
	rr = 1
	for el in arr:
		rr *= el
	return rr
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	tot = 0
	s = 0
	for i in range(len(arr)):
		if arr[i] == 0:
			tot += s * (s + 1) // 2
			s = 0
		else:
			s += 1
	tot += s * (s + 1) // 2
	print(tot)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	sum = 0
	cnt = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			cnt = cnt + 1
			continue
		else:
			sum = sum + cnt * (cnt + 1) // 2
			cnt = 0
	sum += cnt * (cnt + 1) // 2
	print(sum)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(cou, count, k1) = (0, 0, 0)
	for i in range(len(l)):
		if l[i] == 1:
			count += 1
			k1 += 1
			if count == n:
				cou += n * (n - 1) // 2
			elif i == n - 1 and count > 1:
				cou += count * (count - 1) // 2
		elif l[i] == 0:
			if count > 1:
				cou += count * (count - 1) // 2
			count = 0
	print(cou + k1)


for T in range(int(input())):
	N = int(input())
	A = list(map(str, input().split()))
	add = 0
	s = 0
	if A.count('0') == 0:
		s += add * (add + 1) / 2
	for (i, x) in enumerate(A):
		if x == '1':
			add += 1
		if x == '0' or i == N - 1:
			if add != 0:
				s += add * (add + 1) / 2
				add = 0
	print(int(s))


T = int(input())

def count_subarray(n):
	return int(n / 2 * (n + 1))
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	length = 0
	lengths = []
	for bit in a:
		if bit == 1:
			length += 1
		else:
			if length > 0:
				lengths.append(length)
			length = 0
	if length > 0:
		lengths.append(length)
	lengths = map(count_subarray, lengths)
	print(sum(lengths))


t = int(input())
while t > 0:
	t -= 1
	c = 0
	s = 0
	p = int(input())
	a = input().split()
	for i in range(p):
		if int(a[i]) == 0:
			c = 0
		else:
			c = c + 1
			s = s + c
	print(s)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	ans = 0
	lst_ind = [-1]
	for i in range(n):
		if lst[i] == 0:
			lst_ind.append(i)
	lst_ind.append(n)
	for j in range(len(lst_ind) - 1):
		sss = lst_ind[j + 1] - lst_ind[j] - 1
		sum = sss * (sss + 1) / 2
		ans += sum
	print(int(ans))


from functools import cmp_to_key
import math
from pydoc import doc

def run(debug=True):
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		finalAns = 0
		curr = 1
		for i in range(n):
			if arr[i] == 0:
				curr = 1
				continue
			else:
				finalAns += curr
				curr += 1
		print(finalAns)
while True:
	try:
		run(False)
	except:
		break


for _ in range(int(input())):
	B = int(input())
	A = list(map(int, input().split()))
	result = 0
	total = 0
	for i in range(B):
		if A[i] == 0:
			result = 0
		elif A[i] == 1:
			result = result + 1
			total += result
	print(total)


import numpy as np

def F(a, n):
	sum_f = 0
	add = 0
	for l in np.arange(n):
		if a[l] == 0:
			add = 0
		else:
			add += 1
			sum_f += add
	return sum_f
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(F(a, n))


for x in range(int(input())):
	n = int(input())
	l = [int(a) for a in input().split()]
	c = 0
	res = 0
	for d in range(len(l)):
		if l[d] == 0:
			c = 0
		else:
			c += 1
			res += c
	print(res)


def sumofprod(arr, n):
	(ans, res) = (0, 0)
	i = n - 1
	while i >= 0:
		incre = arr[i] * (1 + res)
		ans += incre
		res = incre
		i -= 1
	return ans
t = int(input())
for _ in range(t):
	arr = []
	N = int(input())
	num = input()
	for nn in num:
		if nn != chr(32):
			arr.append(int(nn))
	print(sumofprod(arr, N))


for _ in range(int(input())):
	input()
	arr = list(map(int, input().split(' ')))
	tot_sum = 0
	prev_sum = 0
	for i in range(len(arr)):
		if i > 0 and arr[i - 1] == 1:
			prev_sum -= 1
			tot_sum += prev_sum
			continue
		run_prod = 1
		run_sum = 0
		for j in range(i, len(arr)):
			run_prod *= arr[j]
			if run_prod == 0:
				break
			run_sum += run_prod
		tot_sum += run_sum
		prev_sum = run_sum
	print(tot_sum)


t = int(input())
for nt in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	res = 0
	i = n - 1
	while i >= 0:
		incr = arr[i] * (1 + res)
		ans += incr
		res = incr
		i -= 1
	print(ans)