After spending an hour and a half on the final Mathematics exam, struggling in vain to find the answers to the devilish questions that have come up, you decide it's time to give up, make up the remaining answers, submit, and pray for a passing grade. Fortunately for you, the exam is multiple choice, and each question has three possible options: A, B, or C, and you already know some of the answers. Each correct answer is worth one point, and incorrect answers do not subtract points. You remember from the practice exams you took yesterday that the teacher never puts two consecutive questions with the same answer, meaning that if question 1 is A, then question 2 cannot be A. Your goal is to fill out the exam in such a way that you maximize the number of points you can secure in the worst-case scenario.
The input will consist of an integer $$$t$$$, followed by $$$t$$$ test cases. Each case will have on one line $$$N$$$, the number of questions on the exam, and on the next line a string with $$$N$$$ characters. The $$$i$$$-th character will be 'A', 'B', or 'C' if you know the answer to question $$$i$$$, and '?' if you do not know it.
One line per case with the number of points you can secure on the exam.
33 points: $$$1 \leq N \leq 8$$$, $$$t = 10$$$
11 points: $$$1 \leq N \leq 10^5$$$, $$$t = 50$$$, no two '?' are consecutive.
56 points: $$$1 \leq N \leq 10^5$$$, $$$t = 50$$$
2 6 A??B?C 5 A???A
5 3
