24178번 - ぶりしゃぶしゃぶり部 다국어

문제

次のニュースです.新型コロナウイルスの感染拡大により飲食店以外でのよりよい食事を求める動きが強まる中,ある部活動が注目を集めています.

その名も,ぶりしゃぶしゃぶり部.この新しい活動に取り組む,都内のあるグループを取材しました.

渋谷区のマンションの一室.10 代から 30 代までの若い男女が集まって鍋を囲っています.「このカニもういけるんじゃない?」「あ,ほんとだ」 外から見る限りは,普通のカニ鍋のようです.ぶりですらないようですが……?

このグループの代表を務める男性に話を聞きました. ICPC-JAG (International Collegiate Programming Contest Japanese Alumni Group) 代表 N さん「今日はICPC模擬国内予選の打ち上げです.」 記者「えっ,じゃあぶりしゃぶしゃぶり部というのはいったいなんなんでしょう?」 N さん「ぶりしゃぶしゃぶり部って回文っぽくないですか?」 記者「か,回文……?」 N さん「回文というのは,前から読んでも後ろから読んでも同じになる文のことです.回文っぽいっていうのは,そうですね……」

JAGのメンバーでありこの会話を横で聞きながらカニ鍋をつついていたあなたは,文字列の回文っぽさを判定するプログラムをここで書いてあげれば取材の助けになるかもしれないと思った.ここで,文字列の回文っぽさとは,次のように定められる数である.

• 文字列後半(奇数長のときには中央の文字を含まない)から範囲の重複しない区間を 0 個以上の任意の個数選び,それぞれの区間の部分文字列を反転することで,全体の文字列を回文にすることを考える.回文になる区間の選び方全体が空でないとき,これらのうちそれぞれの区間の長さの二乗の総和の最小値を文字列の回文っぽさとする.回文になる区間の選び方が存在しないとき,回文っぽさは -1 とする.長さ n の文字列 S = S₁ S₂ ... S_n が回文であるとは,任意の i = 1, ..., n に対して S_i = S_n+1-i が成り立つことのみをいう.

입력

入力は 50 個以下のデータセットからなる. 各データセットは次の形式で表される.

S

S は小文字アルファベットからなる文字列であり,1 ≤ |S| ≤ 20000 を満たす.

入力の終わりは # の 1 文字のみからなる行で表される.

출력

各データセットに対し,文字列 S の回文っぽさを 1 行に出力せよ.

제한

힌트