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

题目描述

星野爱是一名充满梦想和活力的偶像。她的日常生活充满了舞台表演、粉丝互动和各种挑战。然而，爱的生活并不仅限于舞台，她还喜欢在闲暇时间解决一些有趣的谜题和问题。

一天，爱在浏览粉丝寄来的礼物时，发现了一个特别的挑战——一串由字符 '-' 和 '_' 组成的字符串。这串字符串是粉丝们为了考验爱的智慧而设计的，他们希望爱能够计算出这串字符串里面最多能够出现多少次 "-_-" 。这个挑战不仅有趣，还能让爱的粉丝更加了解她的多面性。

星野爱需要你的帮助，对于字符串 $s$ 中的各个字符，你可以打乱原字符的顺序，使得"-_-" 出现的次数最大。字符串 $s$ 仅由字符 '-' 和 '_' 组成，你需要计算字符串 $s$ 里面最多能够出现多少次"-_-" （只要“-”与“-”之间存在“_”即可）。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 字符串的长度。

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

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，计算字符串 $s$ 中最多可以出现多少次"-_-" ，请输出这个整数。

输入输出样例

输入

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

输出

1
0
27
2
30
9
0
0

说明/提示

第一个测试用例中，只能出现一次 "-_-" 。

第二个测试用例中只有一个字符 "-"，而构成一个 "-_-" 至少需要两个 "-"，所以答案是 $0$。

第七和第八个测试用例中，字符串长度 $n < 3$，而"-_-"长度为 $3$ ，所以答案是 $0$。

星野爱期待你的帮助，通过智慧和策略，帮助她解开这个有趣的谜题，同时也让她的粉丝更加了解她的多面性和智慧。