問題
レベル$K$の$ABCD$文字列を以下のように定義する。
・文字列の先頭から見たとき、$ABCD$という文字列が最大で$K$回連続している。
例えば、$ABCDABCDABCDDD$はレベル3、$BABCD$はレベル0、$ABCDAABBCCDD$はレベル1の$ABCD$文字列である。
あなたは与えられた文字列Sに対して以下の操作を好きな回数行うことが出来る。
・連続部分文字列$CDAB$を一つ選び、$ABCD$に置き換える。
・$S_i=A$かつ$S_j=B$を満たす$i,j$を一つ選び、$S_i$と$S_j$を入れ替える。
・$S_i=C$かつ$S_j=D$を満たす$i,j$を一つ選び、$S_i$と$S_j$を入れ替える。
操作を終えた後の$ABCD$文字列のレベルを最大化した時のレベルを求めてください。
$T$個のテストケースが与えられるので，それぞれについて答えを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$T$ $case_1$ .各テストケースは以下の形式で与えられます。
.
. $case_T$
$S$
出力
$T$行出力してください。
$i$行目には$case_i$の答えを出力してください。
出力の最後に改行を入れること。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq T \leq 10$
- $1 \leq |S| \leq 2×10^{5}$
- $S$に含まれる文字は$A$,$B$,$C$,$D$のいずれかである。
入出力例
入力例1
5 CDABCDABC BADCBADC AAAABBBBCCD BABCD ABCD
出力例1
2 2 0 0 1
1つ目について、$CDAB$を$ABCD$に置き換える操作を2回行うことでレベル2にすることが可能です。
2つ目について、$A$$とB$、$C$と$D$を置き換える操作をそれぞれ2回ずつ行うことでレベル2にすることが可能です。
3,4つ目について、文字列の先頭から連続している$ABCD$がレベルとして数えられることに注意してください。
5つ目について、操作回数は0回でも構いません。