マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$300$ 点

問題文

P, D, C, A のみからなる文字列を PDCA-String と呼びます．

さらに，PDCA-String $X$ が以下の条件を満たすとき，またそのときに限って $X$ は PDCA-Cyclic であるといいます：

• $X$ の長さ $2$ の連続部分列はすべて PD, DC, CA, AP のいずれかである．

たとえば $3$ PDCA-String DCAPDCAPDCAPDCA, A, DCA はいずれも PDCA-Cyclic です．

長さ $N$ の PDCA-String $S$ があります．

また，次の操作を $0$ 回以上何度でも行えます：

• $1 \leq k \leq N$ なる整数 $k$ を自由に選び，$S$ の $1$ 文字目から $k$ 文字目までを $1$ 要素分だけ左に循環シフトする．すなわち，$S$ を $S' = (S_2, S_3, \ldots, S_{k-1}, S_k, S_1, S_{k+1}, S_{k+2}, \dots, S_N)$ によって定められる文字列 $S' = (S'_1, S'_2, \ldots, S'_N)$ で置き換える．

$S$ が PDCA-Cyclic であるようにすることが目標です．
この目標が達成可能か判定し，できるならばそのために必要な操作回数の最小値を求めてください．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N \leq 10$
• $N$ は整数
• $S$ は長さ $N$ の PDCA-String

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

有限回の操作によって目標を達成できるならば，操作を行う回数の最小値を出力せよ．
どのように操作を行っても目標を達成できないならば -1 と出力せよ．

サンプル

1
5
ACDPP

3

たとえば次のようにして $3$ 回の操作で目標を達成できます：

• $1 \colon k = 4$として操作を行う．
  • $S =$ CDPAP となる．
• $2 \colon k = 3$ として操作を行う．
  • $S =$ DPCAP となる．
• $2 \colon k = 2$ として操作を行う．
  • $S =$ PDCAP となる．
  • このとき $S$ は PDCA-Cyclic である．

どのようにしても $3$ 回未満の操作では目標を達成できないので，$3$ が答えです．

5
6
CAPDCA
3
PCD
5
DACAP
4
PPAP
1
C

0
2
3
-1
0