AT_jsc2026_final_a Avoid Consecutives

英小文字のみからなる文字列 $ S $ が与えられます。 あなたは以下の操作を好きな回数行うことができます。 - $ S $ から文字を $ 1 $ 個選んで取り除き、その文字を $ S $ の（両端を含め）好きな位置に挿入する。 同じ文字が隣り合わないようにできるかを判定し、可能な場合は必要な操作回数の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ S $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 番目のテストケースについて、同じ文字が隣り合わないようにできる場合は必要な操作回数の最小値を出力し、できない場合は `-1` を出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、以下のように操作をすると $ 2 $ 回の操作で同じ文字が隣り合わないようにできます。 - $ 3 $ 文字目の `i` を取り除き、 $ 2 $ 個の `w` の間に挿入する。 $ S $ は `kiiwiw` となる。 - $ 2 $ 文字目の `i` を取り除き、末尾に挿入する。 $ S $ は `kiwiwi` となる。 $ 2 $ つ目のテストケースでは、どのように操作しても $ 2 $ 個の `a` が隣り合います。 ### Constraints - $ 1 \le T \le 10^5 $ - $ 2 \le |S| \le 10^6 $ - $ S $ は英小文字からなる - 全てのテストケースにおける $ |S| $ の総和は $ 10^6 $ 以下 - $ T $ は整数