Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Знаки вопроса
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тим проходит тест, состоящий из $$$4n$$$ вопросов; каждый вопрос имеет $$$4$$$ варианта ответа: 'A', 'B', 'C' и 'D'. Для каждого варианта ответа существует ровно $$$n$$$ правильных ответов, соответствующих этому варианту — это означает, что есть $$$n$$$ вопросов с ответом 'A', $$$n$$$ вопросов с ответом 'B', $$$n$$$ вопросов с ответом 'C' и $$$n$$$ вопросов с ответом 'D'.

Для каждого вопроса Тим записал свой ответ на бланке ответов. Если он не мог определить ответ, он оставлял знак вопроса '?' для этого вопроса.

Вам дан бланк ответов из $$$4n$$$ символов. Какое максимальное количество правильных ответов может получить Тим?

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 100$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ из $$$4n$$$ символов ($$$s_i \in \{\texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}, \texttt{?}\}$$$) — ответы Тима на вопросы.

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

Для каждого набора входных данных выведите одно целое число — максимальный балл, который Тим может получить.

Пример
Входные данные
6
1
ABCD
2
AAAAAAAA
2
AAAABBBB
2
????????
3
ABCABCABCABC
5
ACADC??ACAC?DCAABC?C
Выходные данные
4
2
4
0
9
13
Примечание

В первом наборе входных данных есть ровно один вопрос с каждым ответом 'A', 'B', 'C' и 'D'; поэтому возможно, что Тим получит все свои ответы правильными.

Во втором наборе входных данных есть только два правильных ответа 'A', что делает его результатом ровно $$$2$$$ балла в любом случае.

В третьем наборе входных данных Тим может получить максимум $$$2$$$ правильных ответа с вариантом 'A' и $$$2$$$ правильных ответа с вариантом 'B'. Например, он получил бы $$$4$$$ балла, если бы правильными ответами были 'AACCBBDD'.

В четвертом наборе входных данных он отказывается отвечать на любые вопросы, поэтому его результат в любом случае равен $$$0$$$ баллов.