10716 - Evil Straw Warts Live

Problem D: Evil Straw Warts Live

一個回文字符串被定義為等同於自己本身的反轉。

給定一個字串，其不一定是個回文 ，計算最少的 swap (交換次數) 使這個字串成為回文。
swap 操作定義為交換兩個相鄰字符。

例如字串 "mamad" 可以使用三次 swaps 轉換成回文字串 "madam"：

• swap "ad" 後的結果為 "mamda"
• swap "md" 後的結果為 "madma"
• swap "ma" 後的結果為 "madam" 

測資第一行有一個整數 n 表示接下來的測資組數。
對於每組字串，長度最多為 100 的小寫字母夠成，輸出最少的交換次數，
如果沒辦法轉換成回文字串，則輸出  "Impossible"。

Sample Input

3
mamad
asflkj
aabb

Output for Sample Input

3
Impossible
2

---

Gordon V. Cormack