지우기 2

길이 $N$의 문자열 $S$가 주어진다. $S$는 $\texttt{A}$, $\texttt{B}$, $\texttt{C}$로만 이루어져 있다.

한 번의 연산으로, 현재 문자열에서 서로 다른 두 이웃 문자를 골라 두 문자를 모두 지울 수 있다. 지운 뒤 남은 부분은 이어진다.

연산을 더 이상 할 수 없을 때까지 반복했을 때, 최종적으로 남을 수 있는 서로 다른 문자열의 개수를 구하여라. 빈 문자열도 하나의 문자열로 센다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$

각 테스트 케이스마다 가능한 서로 다른 최종 문자열의 개수를 한 줄에 출력한다.

• $1 \le T \le 2\,000\,000$.
• $1 \le N \le 2\,000\,000$.
• $S$는 $\texttt{A}$, $\texttt{B}$, $\texttt{C}$로만 이루어진 길이 $N$의 문자열이다.
• 모든 테스트 케이스에 대한 $N$의 합은 $2\,000\,000$ 이하이다.