You are given a string S of length N.

Your task is to delete a [subsequence] of maximum length from the string, such that, after concatenating the remaining parts of the string, it becomes a [palindrome] of length greater than 1.

If this is possible, print the maximum length of the subsequence that can be deleted. Otherwise, print -1.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of 2 lines of input:
• The first line consists the a single integer N - the length of string S.
• The second line contains string S, consisting of lowercase english alphabets.

------ Output Format ------

For each test case, if it is possible to delete a subsequence under the given conditions, print a single integer, denoting the maximum length of the subsequence that can be deleted. Otherwise, print -1.

------ Constraints ------

$1 ≤ T ≤ 2500$
$3 ≤ N ≤ 100$
$S$ consists of lowercase english alphabets.

------ subtasks ------

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------
3
6
babkhj
3
abc
4
qtoo
----- Sample Output 1 ------
4
-1
2

----- explanation 1 ------
Test case $1$: Possible ways to delete a subsequence are:
- Delete subsequence khj to get palindrome bab.
- Delete subsequence akhj to get palindrome bb.

The subsequence having maximum length that can be deleted is akhj, having length $4$.

Test case $2$: We cannot delete any subsequence under the given conditions.

Test case $3$: We can delete the subsequence qt to obtain the string oo, which is a palindrome. This is the only subsequence that can be deleted and it has length $2$.

见题面

见题面