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$$$ 分。