题目描述：

给一个字符串，你可以重新排列它。求最多会有多少个子串是回文串。

子串是指原字符串中连续的一段字符串。

回文串是指正读和反读都一样的字符串。

输入格式：

第一行输入一个正整数$T$表示测试组数。

接下来$T$组：

每组第一行输入一个正整数$n$表示字符串长度。

第二行输入一个长度为$n$的字符串$s$。

输出格式：

输出$T$行，每行一个整数表示答案。

样例：

1
4
abab

6

2
20
abababababababababab
50
ababaababaababaababaababaababaababaababaababaababa

110
675

数据约束：

对于$100\%$的数据满足$1\le T\le 100,1\le n\le 10^5,\sum n\le 10^6,s$中仅包含小写字母。