Longest Palindromic Subsequence

You are given a sequence of integers \( S = [s_1, s_2, \dots, s_n] \). Your task is to determine the length of the longest palindromic subsequence in \( S \).

A palindromic subsequence is a sequence that reads the same backward as forward. For example, if \( S = [1, 2, 3, 2, 1] \), the entire sequence is a palindromic subsequence of length 5.

The relation for the dynamic programming solution can be formulated as follows:

\[ \text{if } s_i = s_j: \quad dp[i][j] = \begin{cases} 2 & \text{if } j = i+1 \\ 2 + dp[i+1][j-1] & \text{if } j > i+1 \end{cases} \]

\[ \text{if } s_i \neq s_j: \quad dp[i][j] = \max(dp[i+1][j], dp[i][j-1]) \]

Implement an efficient algorithm to compute the length of the longest palindromic subsequence for each test case.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer \( T \) representing the number of test cases.
• For each test case, the first line contains an integer \( N \) indicating the size of the sequence.
• The second line contains \( N \) space-separated integers representing the sequence \( S \).

outputFormat

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

The output should be written to standard output (stdout).

## sample

2
5
1 2 3 2 1
6
1 2 3 4 2 1

5
5