Solve the programming task below in a Python markdown code block.
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$.