Longest Palindromic Subsequence

Given a string S, your task is to compute the length of the longest palindromic subsequence within S. A subsequence is a sequence that can be derived from the string by deleting some or no characters without changing the order of the remaining characters.

You can use dynamic programming to solve this problem. One common recurrence used is:

\( dp[i][j] = \begin{cases} 1 & \text{if } i = j, \\ 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} \)

For each test case, determine and output the length of the longest palindromic subsequence.

Example:

Input:
1
bbabcbcab
Output:
7

inputFormat

The input begins with an integer T indicating the number of test cases. Each of the following T lines contains a single string S consisting of lowercase letters.

outputFormat

For each test case, output a single integer representing the length of the longest palindromic subsequence for the given string S. Each result should be printed on a new line.## sample

1
bbabcbcab

7