UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1279. Sgu325 palindrome

Statistics 下载数据

Description

回文串的定义就是一个字符串C从前往后读和从后往前读一样。现在给你一个字符串T,每次可以交换2个相邻的字符,你的目标就是通过尽可能少的次数使T变成回文串。如果无解,输出“Impossible”

Input

第1行一个数m,表示有m组数据。下面m行,每行是一个字符串,长度不超过100000。

Output

m行,每行一个数,表示最小交换次数。

Sample Input

2
abab
abc

Sample Output

1
Impossible

Hint

m<=10,n<=100000。

Source