Longest Palindromic Subsequence

Given a string s, your task is to compute the length of the longest subsequence of s that is also a palindrome.

A subsequence is a sequence that can be derived from the string by deleting zero or more characters without changing the order of the remaining characters. A palindrome is a sequence that reads the same backward as forward.

The problem can be formulated using dynamic programming. For a given string s of length n, you can compute a DP table dp where the recurrence is given by:

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

Your solution should read input from standard input and produce the answer for each test case on a new line.

inputFormat

The first line of input contains an integer T indicating the number of test cases. Each of the following T lines contains a non-empty string s.

Example:

2
bbabcbcab
abbaab

outputFormat

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

Example:

7
4

## sample

2
bbabcbcab
abbaab

7
4

</p>