CF1660F1 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中出现的次数相同。

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