该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

给定一个只包含字符 - 和 _ 的字符串。你可以任意重排这个字符串中的字符。

定义一个字符串的价值为：其中等于 -_- 的不同子序列数量。两个子序列如果选择的下标集合不同，就视为不同。

请你求出在最优重排后，字符串价值的最大值。

输入格式

第一行包含一个整数 $t$，表示测试用例数量。

对于每组测试用例：

• 第一行包含一个整数 $n$，表示字符串长度。
• 第二行包含一个长度为 $n$ 的字符串 $s$，仅由 - 和 _ 组成。

输出格式

对于每组测试用例，输出一个整数，表示最优重排后 -_- 子序列数量的最大值。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 2 \times 10^5$
• 所有测试用例的 $n$ 之和不超过 $2 \times 10^5$

样例输入

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

样例输出

1
0
27
2
30
9
0
0

提示

如果 - 的数量不足 $2$，或者 _ 的数量为 $0$，就不可能形成 -_- 子序列，答案为 $0$。