Longest Palindromic Subsequence

You are given a string s of length n. Your task is to find the length of the longest palindromic subsequence in s. A palindromic subsequence is a sequence that reads the same forwards and backwards (not necessarily contiguous). Use a dynamic programming approach where you can define a DP table \(dp[i][j]\) representing the length of the longest palindromic subsequence in the substring \(s[i \ldots j]\). A typical recurrence is:

[ \begin{align*} dp[i][i] &= 1, \ dp[i][j] &= \begin{cases} 2 & \text{if } s[i]=s[j] \text{ and } j-i=1, \ dp[i+1][j-1] + 2 & \text{if } s[i]=s[j] \ \max(dp[i+1][j], dp[i][j-1]) & \text{if } s[i]\neq s[j] \end{cases} \end{align*} ]

Compute the result for each test case.

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. The first line contains an integer T representing the number of test cases. Each test case is defined in two lines:

• The first line contains an integer n which is the length of the string.
• The second line contains the string s.

outputFormat

For each test case, output a single line containing the length of the longest palindromic subsequence in the given string.

## sample

2
6
abcbab
3
aaa

5
3

</p>