This is the easy version of Problem F. The only difference between the easy version and the hard version is the constraints.

We will call a non-empty string balanced if it contains the same number of plus and minus signs. For example: strings "+--+" and "++-+--" are balanced, and strings "+--", "--" and "" are not balanced.

We will call a string promising if the string can be made balanced by several (possibly zero) uses of the following operation:

replace two adjacent minus signs with one plus sign.

In particular, every balanced string is promising. However, the converse is not true: not every promising string is balanced.

For example, the string "-+---" is promising, because you can replace two adjacent minuses with plus and get a balanced string "-++-", or get another balanced string "-+-+".

How many non-empty substrings of the given string $s$ are promising? Each non-empty promising substring must be counted in the answer as many times as it occurs in string $s$.

Recall that a substring is a sequence of consecutive characters of the string. For example, for string "+-+" its substring are: "+-", "-+", "+", "+-+" (the string is a substring of itself) and some others. But the following strings are not its substring: "--", "++", "-++".


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 500$) —the number of test cases in the test.

Then the descriptions of test cases follow.

Each test case of input data consists of two lines. The first line consists of the number $n$ ($1 \le n \le 3000$): the length of $s$.

The second line of the test case contains the string $s$ of length $n$, consisting only of characters "+" and "-".

It is guaranteed that the sum of values $n$ over all test cases does not exceed $3000$.


-----Output-----

For each test case, print a single number: the number of the promising non-empty substrings of string $s$. Each non-empty promising substring must be counted in the answer as many times as it occurs in string $s$.


-----Examples-----

Input
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
Output
2
4
2
7
4


-----Note-----

The following are the promising substrings for the first three test cases in the example:

$s[1 \dots 2]$="+-", $s[2 \dots 3]$="-+";

$s[1 \dots 2]$="-+", $s[2 \dots 3]$="+-", $s[1 \dots 5]$="-+---", $s[3 \dots 5]$="---";

$s[1 \dots 3]$="---", $s[2 \dots 4]$="---".

Difficulty: MEDIUM_HARD
Tags: Mathematics

String algorithms

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
tst = int(input())
for _ in range(tst):
	n = int(input())
	s = input()
	f = [0 for i in range(3)]
	cur_bal = n
	cnt_bal = [0 for i in range(2 * n + 1)]
	cnt_bal[cur_bal] += 1
	f[cur_bal % 3] += 1
	ans = 0
	for i in range(n):
		new_bal = cur_bal
		if s[i] == '-':
			new_bal -= 1
			f[new_bal % 3] += cnt_bal[new_bal]
			ans += f[new_bal % 3]
			cnt_bal[new_bal] += 1
			f[new_bal % 3] += 1
		else:
			f[new_bal % 3] -= cnt_bal[new_bal]
			new_bal += 1
			ans += f[new_bal % 3]
			cnt_bal[new_bal] += 1
			f[new_bal % 3] += 1
		cur_bal = new_bal
	print(ans)


import collections
for _ in range(int(input())):
	n = int(input())
	l = 2 * n + 2
	s = input().strip()
	y = [[0] * (l + 1) for i in range(3)]

	def upd(x, a):
		while x <= l:
			a[x] += 1
			x += x & -x

	def qry(x, a):
		r = 0
		while x > 0:
			r += a[x]
			x -= x & -x
		return r
	ans = 0
	t = n + 1
	upd(t, y[t % 3])
	for i in s:
		t = t + (1 if i == '-' else -1)
		ans += qry(t, y[t % 3])
		upd(t, y[t % 3])
	print(ans)


def promisingstring(s):
	n = len(s)
	presum = [0] * (n + 1)
	ans = 0
	for i in range(1, n + 1):
		if s[i - 1] == '+':
			presum[i] = presum[i - 1] + 1
		else:
			presum[i] = presum[i - 1] - 1
	for i in range(1, n + 1):
		for j in range(i):
			if presum[i] - presum[j] <= 0 and (presum[i] - presum[j]) % 3 == 0:
				ans += 1
	return ans
t = int(input())
for _ in range(t):
	_ = input()
	s = input()
	print(promisingstring(s))


def solve():
	n = int(input())
	s = input()
	ans = 0
	for i in range(n):
		(plus, minus) = (0, 0)
		for j in range(i, n):
			if s[j] == '-':
				minus += 1
			else:
				plus += 1
			ans += minus >= plus and (minus - plus) % 3 == 0
	print(ans)
tst = int(input())
for i in range(tst):
	solve()


tst = int(input())
for _ in range(tst):
	n = int(input())
	s = input()
	b = [0 for i in range(n + 1)]
	bal = n
	b[0] = bal
	ans = 0
	for i in range(1, n + 1):
		if s[i - 1] == '+':
			bal += 1
		else:
			bal -= 1
		b[i] = bal
		for j in range(i):
			if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0:
				ans += 1
	print(ans)


def solution():
	n = int(input())
	s = input()
	ans = 0
	for i in range(n):
		record = {'+': 0, '-': 0}
		for j in range(i, n):
			record[s[j]] += 1
			dif = record['-'] - record['+']
			ans += dif >= 0 and dif % 3 == 0
	print(ans)
t = int(input())
for _ in range(t):
	solution()


from collections import defaultdict
tests = int(input())
for _ in range(tests):
	n = int(input())
	arr = input()
	count = defaultdict(int)
	_max = n
	count[0] = _max
	substrings = 0
	for i in range(1, n + 1):
		if arr[i - 1] == '+':
			_max += 1
		else:
			_max -= 1
		count[i] = _max
		for j in range(i):
			if count[j] >= count[i] and (count[j] - count[i]) % 3 == 0:
				substrings += 1
	print(substrings)


import math
t = int(input())
while t > 0:
	n = int(input())
	s = input()
	p = 0
	ne = 0
	(pos, neg) = ([], [])
	for i in range(n):
		if s[i] == '+':
			p += 1
		else:
			ne += 1
		pos.append(p)
		neg.append(ne)
	count = 0
	for i in range(n):
		a = 0
		b = 0
		for j in range(i, n):
			if s[j] == '+':
				a += 1
			else:
				b += 1
			if b >= a and (b - a) % 3 == 0:
				count += 1
	print(count)
	t -= 1


def promising(x):
	if not x % 3 and x > -1:
		return 1
	return 0
for tc in range(int(input())):
	(count, n, balance) = (0, int(input()), [1 if char == '-' else -1 for char in input()])
	for i in range(n - 1):
		x = sum(balance[i:i + 2])
		count += promising(x)
		for j in range(i + 2, n):
			x += balance[j]
			count += promising(x)
	print(count)


ans = []
for i in range(int(input())):
	n = int(input())
	inpstr = list(input().strip())
	balance = []
	bal = n
	balance.append(bal)
	cnt = 0
	for _ in range(1, n + 1):
		if inpstr[_ - 1] == '+':
			bal += 1
		else:
			bal -= 1
		balance.append(bal)
		for __ in range(_):
			if (balance[__] >= balance[_]) & ((balance[__] - balance[_]) % 3 == 0):
				cnt += 1
	ans.append(cnt)
for answ in ans:
	print(answ)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	pr = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if s[i - 1] == '-':
			pr[i] = pr[i - 1] + 1
		else:
			pr[i] = pr[i - 1] - 1
	c = 0
	for r in range(n + 1):
		for l in range(r):
			if pr[r] - pr[l] >= 0 and (pr[r] - pr[l]) % 3 == 0:
				c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = 0
	for i in range(len(s)):
		(p, m) = (0, 0)
		for j in range(i, len(s)):
			if s[j] == '+':
				p = p + 1
			elif s[j] == '-':
				m = m + 1
			if m >= p and (m - p) % 3 == 0:
				ans = ans + 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	promising = 0
	for i in range(n):
		plus = 0
		minus = 0
		for j in range(i, n):
			if s[j] == '+':
				plus += 1
			elif s[j] == '-':
				minus += 1
			if plus <= minus and (minus - plus) % 3 == 0:
				promising += 1
	print(promising)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	se = set()
	lsta = []
	for j in range(n - 1):
		p = 0
		m = 0
		for k in range(j, n):
			if s[k] == '+':
				p += 1
			else:
				m += 1
			if p == m:
				lsta.append(1)
				c += 1
			elif m > p:
				if (m - p) % 3 == 0:
					lsta.append(1)
	print(len(lsta))


for i in range(int(input())):
	n = int(input())
	s = input()
	a = 0
	for i in range(n):
		p = 0
		m = 0
		for j in range(i, n):
			if s[j] == '+':
				p += 1
			else:
				m += 1
			a += (m - p) % 3 == 0 and m >= p
	print(a)


testcase = int(input())
for _ in range(testcase):
	ans = 0
	length = int(input())
	string = input()
	for i in range(length):
		plus = minus = 0
		for j in range(i, length):
			if string[j] == '+':
				plus += 1
			else:
				minus += 1
			if minus < plus:
				continue
			if (plus - minus) * 2 % 3 == 0:
				ans += 1
	print(ans)


n = int(input())
for i in range(n):
	t = int(input())
	l = input()
	m = 0
	c = 0
	R = []
	for (j, ch) in enumerate(l):
		if ch == '-':
			a = 1
		else:
			a = -1
		f = []
		if j == 0:
			f.append(a)
			if a < 0:
				a = 0
			elif a == 0:
				m = m + 1
			elif a % 3 == 0:
				m += 1
		else:
			f.append(a)
			if a < 0:
				a = -1
			elif a == 0:
				m = m + 1
			elif a % 3 == 0:
				m += 1
			for i in range(j):
				c = a + R[j - 1][i]
				f.append(c)
				if c < 0:
					c = 0
				elif c == 0:
					m = m + 1
				elif c % 3 == 0:
					m += 1
		R.append(f)
	print(m)


for _ in range(int(input())):
	n = int(input())
	temp = input()
	(subl, plul) = ([0 for i in range(n + 1)], [0 for i in range(n + 1)])
	ans = 0
	for i in range(n):
		if temp[i] == '+':
			plul[i + 1] = plul[i] + 1
			subl[i + 1] = subl[i]
		else:
			subl[i + 1] = subl[i] + 1
			plul[i + 1] = plul[i]
	for i in range(n):
		for j in range(i + 1, n):
			subcount = subl[j + 1] - subl[i]
			addcount = plul[j + 1] - plul[i]
			if (subcount - addcount) % 3 == 0 and subcount >= addcount:
				ans += 1
	print(ans)