题目描述

翁老师的字符串只由字符 - 和 _ 构成，而字符串 $s$ 的价值是字符串 $s$ 的子序列 -_- 的数量。

例如，字符串 -_--_- 的价值是 $6$，因为它有 $6$ 个子序列 -_-：

1. $s_1+s_2+s_3$
2. $s_1+s_2+s_4$
3. $s_1+s_2+s_6$
4. $s_1+s_5+s_6$
5. $s_3+s_5+s_6$
6. $s_4+s_5+s_6$

翁老师要求你重新排列字符串 $s$ 中的字符，从而最大化字符串 $s$ 的价值。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 代表测试数据组数，接下来每一组数据：

• 第一行输入一个整数 $n$ 代表字符串长度。
• 第二行输入一个长度为 $n$ 的字符串 $s$。

输出格式

输出一共输出 $t$ 行，每行一个整数代表答案。

8
3
--_
5
__-__
9
--__-_---
4
_--_
10
_-_-_-_-_-
7
_------
1
-
2
_-

1
0
27
2
30
9
0
0

提示

样例解释

• 第一组数据可以重新排列变成 -_- 使得拥有一个子序列为 -_- 因此输出 $1$。

数据范围

对于 $100\%$ 的数据，$1\le t\le 10^4$，$1\leq n\leq 2\cdot 10^5$，保证 $\sum n\leq 2\cdot 10^5$。每个字符串只由字符 - 和字符 _ 构成。

• 子任务 $1$（$30$ 分）：$n\leq 3$。
• 子任务 $2$（$30$ 分）：保证每个字符串只有一个字符 _。
• 子任务 $3$（$40$ 分）：没有特殊限制。