Alice and Bob are playing a game using a string S of length N. They both have their individual strings which are initially empty.

Both players take alternate turns. Alice starts first.
In Alice's turn, she will:
Choose a prefix of S;
Remove the chosen prefix from S;
Append the prefix to the end of her string.

In Bob's turn, he will:
Choose a suffix of S;
Remove the chosen suffix from S;
Reverse the suffix and append it to the end of his string.

Chef has decided to reward them if the length of the Longest Common Subsequence (LCS) of Alice's and Bob's strings is maximized. Help Chef calculate the length of maximum LCS that can be achieved by Alice and Bob.

Note:
A prefix is obtained by deleting some (possibly zero) elements from the end of the string.
A suffix is obtained by deleting some (possibly zero) elements from the beginning of the string.
Please use fast I/O for input and pypy for python submissions.

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

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines, the first line contains a single integer N denoting the length of the original string.
• The second line contains the original string S.

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

For each test case, output the length of the maximum LCS achievable by Alice and Bob.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5000$
- The sum of $N$ over all test cases won't exceed $5000$.

----- Sample Input 1 ------
3
4
abab
6
abccda
4
aaaa

----- Sample Output 1 ------
1
2
2

----- explanation 1 ------
Test case $1$: In Alice's turn, she can pick the prefix $S[1, 2] =$ ab, and append it to her string. Thus, the remaining string is ab. In Bob's turn, he can pick the suffix $S[1, 2] =$ ab, reverse it, and append to his string.
Thus, Alice's string is ab, and, Bob's string is ba. The length of the longest common subsequence in these two strings is $1$.

Test case $2$: In Alice's turn, she can pick the prefix $S[1, 3] =$ abc, and append it to her string. Thus, the remaining string is cda. In Bob's turn, he can pick the suffix $S[1, 3] =$ cda, reverse it, and append to his string.
Thus, Alice's string is abc, and, Bob's string is adc. The length of the longest common subsequence in these two strings is $2$.

Test case $3$: In Alice's turn, she can pick the prefix $S[1, 2] =$ aa, and append it to her string. Thus, the remaining string is aa. In Bob's turn, he can pick the suffix $S[1, 2] =$ aa, reverse it, and append to his string.
Thus, Alice's string is aa, and, Bob's string is aa. The length of the longest common subsequence in these two strings is $2$.

见题面

见题面