Longest Palindromic Subsequence

You are given a string s. Your task is to find the length of the longest palindromic subsequence in s.

A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining elements. A palindrome is a word or sequence that reads the same backward as forward.

The problem can be solved using dynamic programming. Let \( dp[i][j] \) denote the length of the longest palindromic subsequence of the substring \( s[i..j] \). 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, \\ dp[i+1][j-1] + 2 & \text{if } s[i] = s[j] \text{ and } j-i>1, \\ \max(dp[i+1][j], dp[i][j-1]) & \text{if } s[i] \neq s[j]. \end{cases} \end{aligned} $$

Implement the solution and process multiple test cases from standard input.

inputFormat

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

outputFormat

For each test case, print the length of the longest palindromic subsequence on a new line.

## sample

3
ABBDCACB
AAAA
ABCDE

5
4
1

</p>