你聽過回文樹嗎？這是⼀種可以在 O(N|Σ|) 的時間內算出一個長度為 N 的字串 S 的所有回文子字串出現次數的資料結構，其中 |Σ| 為字元集的大小。例如，當 S 是 abacaba 時，子字串 a 、b 、aba 、aca 、bacab 、abacaba 皆是回文，且其中 aba 出現了兩次、a 出現了四次。

由於回文樹不僅功能強大，種在路邊作為行道樹也可以美化市容。更重要的是，如果用回文來灌溉它的話，它就會將城市中的廢氣轉為清新的空氣！長年受到空氣污染影響的 NPSC 國當然不會放過這個機會，因此 NPSC 國政府從回文樹的原⽣地 CSPN 國購進了大量的回文樹，並打算用大量的回文來灌溉它。

不過，NPSC 國很快就發現了，如果灌溉用的回文的字典序不夠小的話，可能反而造成反效果，使得回文樹枯萎而死。因此，政府打算重新排列手上的字串，使得它變成回文且字典序最小。請幫助 NPSC 國找到字典序最小的回文，解決空汙的問題！ 

輸入第一行有一個正整數 T ，代表回文樹的肥料個數。接著 T 行，每行有⼀個非空字串 S，代表⼀個灌溉用的字串。

• 1 ≤ T ≤ 200
• 輸入字串的總長度不會超過 10⁶ 。
• S 只由大寫英文字母組成。

2
ACCBBA
ABC

ABCCBA
NPSCCSPN