Sgu325Palindrome

时间限制:5s    【提交】    空间限制:64MB

题目描述

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


输入格式

第1行一个数m,表示有m组数据。 下面m行,每行首先是一个数n,表示这一行的字符的长度,接着是一个长为n的字符串。


输出格式

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


样例输入

2
4 abab
3 abc

样例输出

1
Impossible!

提示

没有写明提示


题目来源

没有写明来源