← 返回题目列表

Codeforces · 1993/A

A. 问号

中文机器翻译题面 查看原题

Tim 正在做一个由 $$$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$$$)。

每个测试用例的第二行包含一个由 $$$4n$$$ 个字符组成的字符串 $$$s$$$ ($$$s_i \in \{\texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}, \texttt{?}\}$$$) - Tim 对问题的回答。

输出

对于每个测试用例,打印一个整数 - Tim 可以获得的最高分数。

示例

输入 #1

6
1
ABCD
2
AAAAAAAA
2
AAAABBBB
2
????????
3
ABCABCABCABC
5
ACADC??ACAC?DCAABC?C

输出 #1

4
2
4
0
9
13

注意

在第一个测试用例中,每个答案只有一个问题“A”、“B”、“C”和“D”;所以蒂姆有可能所有的答案都是正确的。

在第二个测试用例中,只有两个正确答案“A”,这使得他在任何情况下都准确地获得 $$$2$$$ 分。

在第三个测试用例中,Tim 使用选项“A”最多可以获得 $$$2$$$ 正确答案,使用选项“B”最多可以获得 $$$2$$$ 正确答案。例如,如果答案是“AACCBBDD”,他将获得 $$$4$$$ 分。

在第四个测试用例中,他根本拒绝回答任何问题,这使他获得 $$$0$$$ 分。