Longest Palindromic Subsequence

Given T strings, your task is to determine the length of the longest palindromic subsequence in each string.

A subsequence of a string 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 are expected to use dynamic programming to solve this problem. In many DP solutions, a 2D table dp is used where:

\( 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} \)

The answer for each test case is the value at dp[0][n-1] where n is the length of the string.

inputFormat

The input is read from stdin and contains multiple lines:

• The first line contains an integer T representing the number of test cases.
• Each of the following T lines contains a non-empty string consisting of lowercase letters.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest palindromic subsequence for the given string. The output is written to stdout.

## sample

2
bbbab
cbbd

4
2

</p>