A. Zoey's Symmetry Emergency
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

At a HUNTR/X concert, $$$n$$$ fans are sitting in one long row, each holding a light stick. The color of each light stick is represented by one lowercase English letter in a string $$$s$$$ of length $$$n$$$.

While Rumi, Mira, and Zoey are getting ready to perform, the fans decide that their row should look as symmetric as possible for a photo because Zoey loves symmetry. They may switch seats in any way they want. After the rearrangement, the sequence of light-stick colors is some permutation $$$p$$$ of $$$s$$$.

Using zero-based indexing, a fan at position $$$i$$$ is called symmetric if

$$$$$$p_i=p_{n-1-i}.$$$$$$

Find the maximum possible number of symmetric fans after rearranging the row.

Input

The first line contains an integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of fans.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters — the light-stick colors.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print one integer — the maximum possible number of symmetric fans.

Example
Input
6
5
abcde
6
aabbcc
7
aaabbcd
4
aaaa
8
abcabcde
1
z
Output
1
6
5
4
6
1
Note

In the first test case, every rearrangement has exactly one fan in the middle of the row, and that fan is symmetric.

In the second test case, the fans can be arranged as $$$abccba$$$, making all $$$6$$$ fans symmetric.

In the third test case, one optimal arrangement is $$$cababad$$$, which has $$$5$$$ symmetric fans.

In the fourth test case, the row is already completely symmetric.

In the fifth test case, the arrangement $$$dabccbae$$$ has $$$6$$$ symmetric fans.

In the sixth test case, the only fan is symmetric.