题目描述

给定一个串 $S$，问其最少经过多少次交换相邻两个字符可以变为回文串，无解输出 Impossible!。

多组询问。

输入格式

第一行一个数 $T$，表示有 $T$ 组数据。

下面 $T$ 行，每行首先是一个数 $n$，表示这一行的字符的长度，接着是一个长为 $n$ 的字符串。

输出格式

$T$ 行，每行一个数，表示最小交换次数，或是一个串 Impossible! 表示无解。

2
4 abab
3 abc

1
Impossible!

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^6$。