Promising String (easy version)

题意翻译

简单版与困难版的区别只有数据范围不同。 我们将一个非空字符串称作平衡字符串当且仅当它有相同数量的加号和减号。举例：字符串“+--+”和“++-+--”是平衡的，字符串“+--”，“--”和“”是不平衡的。 我们将一个字符串称作有希望的字符串当且仅当这个字符串可以通过几次（可能为0次）以下的操作来变成平衡的字符串。 操作： - 将两个相邻的减号换成一个加号 特别的，一个平衡的字符串是一个有希望的字符串，但不是所有有希望的字符串都是平衡的字符串。 举个例子，字符串“-+---”是有希望的，因为你可以将两个相邻的减号换成加号后得到一个平衡的字符串“-++-”，或者“-+-+”。 给定一个字符串 $s$ ， $s$ 的多少个非空子串是有希望的？每个有希望的非空子串在答案中的计数次数必须与在字符串$s$中出现的次数相同。 子串是字符串中一段连续的字符，举例，对于字符串“+-+”来说，它的子串有“+-”，“-+”，“+”，“+-+”（它本身也是它的子串）等一些其他子串，但“--”，“++”，“-++”不是它的子串。 ### 输入格式 第一行有一个整数 $t\ (1 \le t \le 500)$ ，是数据的组数。 接下来是每组数据的描述。 每组数据有两行。第一行有一个整数 $n\ (1 \le n \le 3000)$ ，为 $s$ 的长度。 第二行是一个长度为 $n$ 的字符串 $s$ ，只包含“+”和“-”。 保证每个测试点的 $n$ 的总和不超过 $3000$ 。 ### 输出格式 对于每组数据输出一个整数，表示字符串 $s$ 里非空的有希望的子串的数量。每个非空子串在答案中的计数次数必须与在字符串s中出现的次数相同。

题目描述

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: "--", "++", "-++".

输入输出格式

输入格式

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 $ .

输出格式

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 $ .

输入输出样例

输入样例 #1

5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---

输出样例 #1

2
4
2
7
4

说明

The following are the promising substrings for the first three test cases in the example: 1. $ s[1 \dots 2] $ ="+-", $ s[2 \dots 3] $ ="-+"; 2. $ s[1 \dots 2] $ ="-+", $ s[2 \dots 3] $ ="+-", $ s[1 \dots 5] $ ="-+---", $ s[3 \dots 5] $ ="---"; 3. $ s[1 \dots 3] $ ="---", $ s[2 \dots 4] $ ="---".