CF1660F1.Promising String (easy version)

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

这是问题 F 的简单版本。简单版本与困难版本的唯一区别在于约束条件。

我们称一个非空字符串是平衡的，如果它包含相同数量的加号（+）和减号（-）。例如：字符串 "+--+" 和 "++-+-" 是平衡的，而字符串 "+--"、"--" 和空字符串 "" 则不是平衡的。

我们称一个字符串是有希望的（promising），如果可以通过若干次（可能为零次）以下操作将其变为一个平衡字符串：

• 将两个相邻的减号替换为一个加号。

特别地，每个平衡字符串都是有希望的。但其逆命题不成立：并非每个有希望的字符串都是平衡的。

例如，字符串 "-+--" 是有希望的，因为你可以将两个相邻的减号替换为加号，从而得到一个平衡字符串 "-++-"，或者得到另一个平衡字符串 "-+-+"。

给定字符串 $s$，它有多少个非空子串是有希望的？每个非空的有希望子串在答案中应被计数的次数，等于它在字符串 $s$ 中出现的次数。

注意：子串是指字符串中连续的一段字符构成的序列。例如，对于字符串 "+-+"，它的子串包括："+-"、"-+"、"+"、"+-+"（字符串本身也是其子串）等；但以下字符串不是它的子串："--"、"++"、"-++"。

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

输入的第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。

随后是各测试用例的描述。

每个测试用例包含两行。第一行为一个整数 $n$（$1 \le n \le 3000$）：字符串 $s$ 的长度。

测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串仅由字符 "+" 和 "-" 组成。

保证所有测试用例的 $n$ 值之和不超过 $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$.

对于每个测试用例，输出一个整数：字符串 $s$ 中“有希望的”非空子串的数量。每个非空的“有希望的”子串在答案中应被计数的次数，等于其在字符串 $s$ 中出现的次数。

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]$="---".

以下是示例中前三个测试用例的“有希望子串”：

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]$="---".