Read problems statements in Mandarin Chinese  and Russian. 

Given a string S consisting of only 1s and 0s, find the number of substrings which start and end both in 1.

In this problem, a substring is defined as a sequence of continuous characters S_{i}, S_{i+1}, ..., S_{j} where 1 ≤ i ≤ j ≤ N.

------ Input ------ 

First line contains T, the number of testcases. Each testcase consists of N(the length of string) in one line and string in second line.

------ Output ------ 

For each testcase, print the required answer in one line.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$Sum of  N  over all testcases ≤ 10^{5}$

----- Sample Input 1 ------ 
2
4
1111
5
10001
----- Sample Output 1 ------ 
10
3
----- explanation 1 ------ 
Test case $1$: All substrings of this string start and end with 1. The substrings are $\{ 1, 1, 1, 1, 11, 11, 11, 111, 111, 1111 \}$. The total count of these substrings is $10$.

Test case $2$: Three substrings of this string start and end with 1. These are $\{1, 1, 10001\}$.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Combinatorics

Data structures

Mathematics


Solutions:
from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	c = s.count('1')
	print(c * (c + 1) // 2)


for t in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	print(a * (a + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	a = input()
	c = a.count('1')
	print(c * (c + 1) // 2)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	count = 0
	for x in S:
		if x == '1':
			count += 1
	print(count * (count + 1) // 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	x = s.count('1')
	s1 = 0
	for i in range(1, x + 1):
		s1 += i
	print(s1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in s:
		if i == '1':
			c += 1
	print(c * (c + 1) // 2)


T = int(input())
for i in range(T):
	N = int(input())
	s = input()
	n = s.count('1')
	print(int(n * (n + 1) / 2))


T = int(input())
while T:
	n = int(input())
	s = input()
	c = s.count('1')
	print(c * (c + 1) // 2)
	T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	k = s.count('1')
	print(int(k * (k + 1) / 2))


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	p = a * (a - 1)
	ans = a + p // 2
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = list(input())
	ct = s.count('1')
	summ = ct
	ct -= 1
	while ct >= 0:
		summ += ct
		ct -= 1
	print(summ)


t = int(input())
for r in range(t):
	n = int(input())
	s = input()
	a = s.split('1')
	m = len(a) * (len(a) - 1) // 2
	print(m)


i = int(input())
for _ in range(i):
	a = int(input())
	b = input()
	p = 0
	for t in range(b.count('1') + 1):
		p = p + t
	print(p)


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	cnt = string.count('1')
	print(cnt * (cnt + 1) // 2)


t = int(input())
while t:
	n = int(input())
	s = input()
	c = s.count('1')
	print(c * (c + 1) // 2)
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = input()
	k = l.count('1')
	print(k * (k + 1) // 2)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = str(input())
	ones = data.count('1')
	sol = 0
	for i in range(1, ones + 1):
		sol = sol + i
	print(sol)


t = int(input())
for ccij in range(t):
	n = int(input())
	s = str(input())
	num = s.count('1')
	print(num * (num + 1) // 2)


for _ in range(int(input())):
	N = int(input())
	S = input().strip()
	ones = S.count('1')
	print(ones + ones * (ones - 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()[:n]
	a = s.count('1')
	result = 0
	if '1' in s:
		result = a * (a + 1) // 2
	print(result)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = input('')
	k = list(t)
	c = 0
	for j in k:
		if j == '1':
			c = c + 1
	ans = 0
	for f in range(1, c + 1):
		ans = ans + f
	print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	temp = s.count('1')
	print(temp * (temp + 1) // 2)


for _ in range(int(input())):
	T = int(input())
	N = input().strip()
	M = N.count('1')
	print(M * (M + 1) // 2)


T = int(input())
for test_case in range(T):
	N = int(input())
	S = input()
	num_1 = S.count('1')
	print(num_1 * (num_1 + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	cnt = s.count('1')
	res = cnt * (cnt + 1) // 2
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split('1')
	mn = len(a) * (len(a) - 1) // 2
	print(mn)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	x = 0
	y = 0
	for i in s:
		if i == '1':
			x += 1
	for i in range(x + 1):
		y += i
	print(y)


for _ in range(int(input())):
	n = int(input())
	s = input()
	(res, valid) = (0, 0)
	for c in s:
		if c == str(1):
			valid += 1
			res += valid
	print(res)


a = int(input())
i = 0
while i < a:
	b = int(input())
	c = input()
	d = 0
	for j in range(b):
		if c[j] == '1':
			d += 1
	e = d + d * (d - 1) // 2
	print(e)
	i += 1


for i in range(int(input())):
	n = int(input())
	st = input()
	count1 = 0
	for x in st:
		if x == '1':
			count1 += 1
	print(count1 * (count1 + 1) // 2)


for x in range(int(input())):
	n = int(input())
	s = input()
	c = s.count('1')
	fc = 1
	de = 1
	for i in range(1, c + 1):
		fc = fc * i
	for i in range(1, c - 1):
		de = de * i
	g = fc // (de * 2)
	print(int(c) + g)


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = list(s).count('1')
	print(x * (x + 1) // 2)


tc = int(input())
for i in range(tc):
	n = int(input())
	s = list(input())
	ans = s.count('1')
	print(ans * (ans + 1) // 2)


t = int(input())
for i in range(0, t):
	n = int(input())
	lst = [str(i) for i in input()][:n]
	temp = 0
	for i in lst:
		if i == '1':
			temp += 1
	print(temp * (temp + 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = str(input())
	lt = []
	for i in range(len(a)):
		if a[i] == '1':
			lt.append(i)
	print(len(lt) * (len(lt) + 1) // 2)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = input()
	ans = a.count('1')
	y = ans * (ans + 1) // 2
	print(y)


from collections import Counter, UserString
from math import log2
mod = lambda n: int(n % (10 ** 9 + 7))
_fc = [1]
for i in range(1, 1000001):
	_fc.append(i * _fc[i - 1])
	_fc[i] = mod(_fc[i])

def fact(n):
	if -1000001 < n < 1000001:
		if n > -1:
			return _fc[n]
		else:
			return -_fc[abs(n)]
	else:
		raise ValueError('values only from 1000000 to -1000000 can be factorialized\n')

def yn(b, caps=False, y='Yes', n='No'):
	if b:
		returning = y
	else:
		returning = n
	if caps == 2:
		return returning.lower()
	elif caps == 3:
		return ''.join([returning[i].lower() if i % 2 == 0 else returning[i].upper() for i in range(len(returning))])
	elif caps:
		return returning.upper()
	return returning

def prob(l, n):
	return l.count(n) / len(l)

def isSubseq(s1, s2):
	(n, m) = (len(s1), len(s2))
	(i, j) = (0, 0)
	while i < n and j < m:
		if s1[i] == s2[j]:
			i += 1
		j += 1
	return i == n

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

def percentDiff(n, diff):
	return n + n * (diff / 100)

def prodLst(l1, nl):
	if isinstance(nl, int):
		return [i * nl for i in l1]
	else:
		return [i * j for (i, j) in zip(l1, nl)]

def divLst(l1, nl, mxMn=False):
	if isinstance(nl, int):
		return [i // nl for i in l1]
	elif mxMn:
		return [max(i, j) // min(i, j) for (i, j) in zip(l1, nl)]
	else:
		return [i // j for (i, j) in zip(l1, nl)]

def modLst(l, n):
	return [i % n for i in l]

def sumLst(l1, nl):
	if isinstance(nl, int):
		return [i + nl for i in l1]
	else:
		return [i + j for (i, j) in zip(l1, nl)]

def absLst(l):
	return [abs(i) for i in l]

def diffLst(l1, nl, isAbs=False):
	if isinstance(nl, int):
		returning = [i - nl for i in l1]
	else:
		returning = [i - j for (i, j) in zip(l1, nl)]
	if isAbs:
		return absLst(returning)
	else:
		return returning

def remCommonOccurs(l, remLst):
	srl = set(remLst)
	returning = []
	for i in l:
		if i not in remLst:
			returning.append(i)
	return returning

def remPosNeg(l, posNeg=False):
	returning = []
	if not posNeg:
		for i in l:
			if i >= 0:
				returning.append(i)
	else:
		for i in l:
			if i < 0:
				returning.append(i)
	return returning

def flip(nl):
	if isinstance(nl, int):
		return -nl
	elif isinstance(nl, list):
		return [-i for i in nl]

def ev(n):
	return not n & 1

def decimal(n):
	returning = int(n)
	if list(set(str(n)[str(n).index('.') + 1:])) == ['0']:
		return returning
	else:
		return returning + 1

def printdeci(n):
	print(decimal(n))

def printabs(n):
	print(abs(n))

def printm(n):
	print(mod(n))

def printy(b, caps=False, y='Yes', n='No'):
	print(yn(b, caps, y, n))

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
listToStr = lambda l: ''.join(map(str, l))
bint = lambda b: int(str(b), 2)
r2 = lambda n: range(1, n + 1)
rl = lambda *l: range(len(l[0])) if len(l) == 1 else range(l[0], len(l[1]))
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(str(input()))
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	lenOfStr = ii()
	inpStr = si()
	ans = inpStr.count('1')
	ans = ans * (ans + 1) // 2
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	s = str(input())
	f = s.count('1')
	print(f + f * (f - 1) // 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = s.count('1')
	print(c * (c + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	c = 0
	for i in range(1, a + 1):
		c += i
	print(c)


for i in range(int(input())):
	n = int(input())
	s = input()
	ct = s.count('1')
	em = 0
	for j in range(1, ct + 1):
		em += j
	print(em)


t = int(input())
while t:
	n = int(input())
	s = input()
	ones = s.count('1')
	total = int(ones * (ones + 1) / 2)
	print(total)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	input_string = input()
	test = 0
	for j in range(0, n):
		if input_string[j] == '1':
			test += 1
	print(int(test * (test + 1) / 2))


T = int(input())
for t in range(T):
	N = int(input())
	S = input()
	prev_count = 0
	cur_count = 0
	for i in range(len(S)):
		if S[i] == '1':
			cur_count += 1
			cur_count += prev_count
			prev_count += 1
	print(cur_count)


for i in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	for i in range(len(s)):
		ch = s[i]
		if s[i] == '1':
			c += 1
	print(c * (c + 1) // 2)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = input()
	c = arr.count('1')
	print(c * (c + 1) // 2)


a = int(input())
for i in range(a):
	b = int(input())
	c = list(input())
	single = c.count('1')
	total = 0
	while single > 0:
		total += single
		single -= 1
	print(total)


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	o = s.count('1')
	print(o * (o + 1) // 2)


casos = int(input())
for i in range(casos):
	nro_caracteres = int(input())
	cadena = input()
	lista = []
	suma = 0
	for i in cadena:
		if i == '1':
			lista.append(i)
	for (x, i) in enumerate(lista):
		suma += x + 1
	print(suma)


t = int(input())
for ii in range(t):
	n = int(input())
	li = input()
	cnt = 0
	for i in li:
		if i == '1':
			cnt += 1
	print(cnt * (cnt + 1) // 2)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ones = s.count('1')
	ans = 0
	if ones == '0':
		print(0)
	else:
		for i in range(1, ones + 1):
			ans += i
		print(ans)


for i in range(int(input())):
	a = int(input())
	m = input()
	n = m.count('1')
	r = 0
	for j in range(1, n + 1):
		r += j
	print(r)


for t in range(int(input())):
	N = int(input())
	S = list(input())
	n = S.count('1')
	print(int(n / 2 * (2 + (n - 1))))


t = int(input())
for _ in range(t):
	n = input()
	s = input()
	count = 0
	for i in s:
		if i == '1':
			count += 1
	prod = count * (count - 1)
	ans = count + prod // 2
	print(ans)


x = int(input())
for i in range(x):
	N = int(input())
	stri = input()
	no1 = 0
	for k in range(N):
		if stri[k] == '1':
			no1 += 1
	print(no1 + no1 * (no1 - 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = 0
	for j in s:
		if j == '1':
			count += 1
	ans = count * (count + 1) // 2
	print(ans)


t = int(input(''))
if 1 <= t <= 10 ** 5:
	for _ in range(t):
		sum = 0
		n = int(input(''))
		s = input('')
		x = s.count('1')
		print(x * (x + 1) // 2)


def triangle(m):
	tri = 0
	while m > 0:
		tri += m
		m -= 1
	return tri
for tc in range(int(input())):
	n = int(input())
	s = input()
	print(triangle(s.count('1')))


for t in range(int(input())):
	n = int(input())
	a = input()
	c = a.count('1')
	ans = 0
	while c != 0:
		ans = ans + c
		c = c - 1
	print(ans)


for _ in range(int(input())):
	N = int(input())
	S = input()
	c = S.count('1')
	print(c * (c + 1) // 2)


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	s1 = s.count('1')
	print(int(s1 * (s1 + 1) / 2))