Longest Palindromic Subsequence Problem Statement

Ninja receives a PS5 from Santa, locked in a safe with a password. The password is the length of the longest palindromic subsequence in the given string SECRETCODE. Can you determine this password to help Ninja open the safe?

Input:

The first line contains an integer 'T', indicating the number of test cases. Each test case has two lines: the first line is an integer 'N' representing the length of the string 'SECRETCODE', and the second line contains the string 'SECRETCODE'.

Output:

For each test case, output a single integer on a new line, which is the length of the longest palindromic subsequence in 'SECRETCODE'.

Example:

Input: 
2
7
CACBDBA
3
AAA
Output: 
4
3

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10³

Note: 'SECRETCODE' consists only of English uppercase letters.