Sgu325Palindrome

回文串是指从前往后读和从后往前读都相同的字符串。

现在给定一个字符串 $T$，每次可以交换两个相邻的字符。请计算至少需要进行多少次交换，才能将 $T$ 变成回文串。

如果无法通过交换得到回文串，请输出 Impossible!。

输入格式

第 $1$ 行包含一个整数 $m$，表示数据组数。

接下来 $m$ 行，每行包含一个整数 $n$ 和一个长度为 $n$ 的字符串，分别表示字符串的长度和字符串本身。

输出格式

输出 $m$ 行，每行一个整数，表示将对应字符串变成回文串所需的最少交换次数。

如果无法得到回文串，则输出 Impossible!。

样例输入

2
4 abab
3 abc

样例输出

1
Impossible!

数据范围

原题未给出明确的数据范围。

来源与许可

本题题面与测试数据整理自 BZOJ 1437。

样例 1

输入

2
4 abab
3 abc

输出

1
Impossible!