B. Будучи казначеем в прошлом, я помогаю гоблинам обманывать людей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После выполнения первого квеста Акито вышел из начальной пещеры. Через некоторое время он набрел на гоблинскую деревню.

Так как жить Акито негде, он захотел узнать цену жилья. Всем известно, что числа гоблины записывают в виде строки из символов '-' и '_', а значением, записанным строкой $$$s$$$, числа является количество различных подпоследовательностей$$$^{\text{∗}}$$$ строки $$$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$$$ так, чтобы значение числа, записанного строкой $$$s$$$, было максимально.

$$$^{\text{∗}}$$$Подпоследовательностью строки $$$a$$$ назовем строку $$$b$$$, которую можно получить, удалив из $$$a$$$ несколько (возможно, $$$0$$$) символов. Подпоследовательности считаются различными, если для их получения были удалены различные множества индексов.

Входные данные

В первой строке дано число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов данных.

В первой строке каждого набора данных дано одно число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строки, которую написали гоблины.

Во второй строке каждого набора данных дана строка $$$s$$$ длины $$$n$$$, состоящая только из символов '-' и '_' — строка, которую записали гоблины.

Гарантируется, что сумма $$$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$$$ не существует.