Longest Palindromic Subsequence

You are given a string S. A palindrome is a string that reads the same backward as forward. In this problem, you need to compute the length of the longest subsequence of S that is a palindrome. A subsequence is a sequence derived from the string by deleting zero or more characters without changing the order of the remaining characters.

The solution is expected to use a dynamic programming approach. For example, for the string "abca", the longest palindromic subsequence is "aba", and its length is 3.

Read the input from stdin and output the result(s) to stdout.

inputFormat

The first line contains an integer T, representing the number of test cases. Each of the following T lines contains a string S.

outputFormat

For each test case, output a single line containing the length of the longest palindromic subsequence in the given string.## sample

1
abca

3