Bi_lindrome!

Difficulty Rating:1095            @Codechef

Problem

You are given a string $�$ of length $�$.

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 $�$, denoting the number of test cases.
• Each test case consists of $2$ lines of input:
  • The first line consists the a single integer $�$ - the length of string $�$.
  • The second line contains string $�$, 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\le �\le 2500$
• $3\le �\le 100$
• $�$ consists of lowercase english alphabets.

Sample 1:

Input                                           Output