完成第一个任务后,明人离开了起始洞穴。过了一会儿,他偶然发现了一个哥布林村庄。
由于 Akito 无处可住,他想了解一下房价。众所周知,妖精们把数字写成‘-’和‘_’组成的字符串,字符串$$$s$$$表示的值就是字符串$$$s$$$中与字符串“相等的不同子序列$$$^{\text{*}}$$$的个数。-_-”(这与妖精的面孔非常相似)。
例如,字符串 $$$s=$$$"-_--_-“代表数字$$$6$$$,因为它有$$$6$$$子序列”-_-":
- $$$s_1+s_2+s_3$$$
- $$$s_1+s_2+s_4$$$
- $$$s_1+s_2+s_6$$$
- $$$s_1+s_5+s_6$$$
- $$$s_3+s_5+s_6$$$
- $$$s_4+s_5+s_6$$$
最初,妖精们写了一个随机的字符串数字 $$$s$$$ 来回答 Akito 的问题,但后来他们意识到他们想从旅行者那里拿走尽可能多的黄金。为此,他们要求您重新排列字符串 $$$s$$$ 中的字符,以便最大化字符串 $$$s$$$ 表示的数字的值。
$$$^{\text{*}}$$$字符串 $$$a$$$ 的子序列是字符串 $$$b$$$,可以通过从 $$$a$$$ 中删除几个(可能是 $$$0$$$)字符来获得。如果子序列是通过删除不同的索引集而获得的,则认为它们是不同的。
输入
第一行包含数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
在每个测试用例的第一行,有一个数字$$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)——小妖精写入的字符串的长度。
在每个测试用例的第二行中,有一个长度为$$$n$$$的字符串$$$s$$$,仅由字符“-”和“_”组成——这是妖精写的字符串。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,您需要输出一个数字 - 如果字符串 $$$s$$$ 中的字符经过最佳重新排列,则子序列的最大数量等于字符串“-_-”。
示例
输入复制
83--_5__-__9--__-_---4_--_10_-_-_-_-_-7_------1-2_-
输出复制
1 0 27 2 30 9 0 0
注意
在第一个测试用例中,重新排列字符以形成字符串“-_-”是有益的。这是唯一一个至少有一个子序列“-_-”的三个字符的字符串。
在第二个测试用例中,只有一个字符“-”,子序列“-_-”至少需要两个字符。这意味着对于任何字符重新排列,答案将是 $$$0$$$。
在第七个和第八个测试用例中,字符串 $$$n \lt 3$$$ 的长度,这意味着长度为 $$$3$$$ 的子序列不存在。