L - Very Long koyaso
Flavor
2
s
1024
MB
100
点
問題文
正整数 $N$ と、英小文字からなる文字列 $S _ 1, S _ 2,\ldots ,S _ N$ が与えられます。
以下の条件を満たすような最大の正整数 $k$ を求めてください。ただし、どの正整数 $k$ についても条件を満たせない場合は $0$ を答えてください。
- $S _ 1, S _ 2,\ldots ,S _ N$ をちょうど $1$ 回ずつ使い、好きな順番で連結して $1$ つの文字列 $X$ を作る。このとき $X$ が部分文字列として
koyaa...aaso（aは $k$ 個）を含むようにできる。
$1$ 回の実行で $T$ 個 ($1\leq T$) のテストケースについて解いてください。
制約
- $1 \leq T \leq 100$
- $N$ は整数で、 $1 \leq N \leq 30$
- $S _ i$ は英小文字からなる文字列
- $S _ i$ の長さは $1$ 以上 $30$ 以下である
入力
$1$ 行目にテストケースの個数 $T$ が入力されます。
$2$ 行目以降、 $T$ 個のテストケースが順に入力されます。各テストケースは以下の形式で与えられます。
$N$
$S _ 1$
$S _ 2$
$\vdots$
$S _ N$
出力
各テストケースについて、順に、問題文に従って $k$ の最大値または $0$ を出力してください。
出力は改行で区切ってください。
入力例 1
3
4
iiiiiko
soooooo
yaaaaaa
zzzzzzz
1
nationalkoyasouniversity
3
koyaaaaaan
soso
koyso
出力例 1
6
1
0
$1$ 個目のテストケースでは、 $S _ 1$ , $S _ 3$ , $S _ 2$ , $S _ 4$ の順に連結すると文字列 $X$ は iiiiikoyaaaaaasoooooozzzzzzz となり、これは部分文字列 koyaaaaaaso を含むため、 $k=6$ が条件を満たします。
$3$ 個目のテストケースでは、条件を満たす正整数 $k$ が存在しないため、 $0$ を出力する必要があります。