英小文字からなる文字列 $S$ と、初めは空の文字列 $T$ が与えられます。

$S$ が空文字列になるまで何回かの操作を行います。各回で、次の三種類の操作のうち一つを行えます:

• $S$ の最初の文字を削除し、それを $T$ の末尾に追加する。
• $S$ の最後の文字を削除し、それを $T$ の末尾に追加する。
• $S=ABA^R$ を満たす空でない文字列 $A,B$ を選び、$S=B$ として文字列 $A$ を $T$ の末尾に追加する。

ここで $A^R$ は文字列 $A$ を反転した文字列を表します。

すべての操作方法の中で得られる、辞書順で最小の $T$ を求めてください。

入力

この問題には複数のテストケースがあります。

最初の行にはテストケースの数を表す正整数 $t$ ($1\le t\le 10^5$) が入力されます。

各テストケースについて:

一行に小文字からなる文字列 $S$ ($1\le |S|\le 5\times 10^5$) が入力されます。

すべてのテストケースにわたる $|S|$ の合計は $5\times 10^5$ 以下であることが保証されます。

出力

各テストケースについて、答えを表す文字列を一行に出力してください。

入出力例

入力 1

6
cba
zayaz
aaaaa
xazbx
ababa
aa

出力 1

abc
zaay
aaa
xabz
aaba
aa