Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/65535 K (Java/Others)

In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence <A, B, D> is a subsequence of <A, B, C, D, E, F>.

(http://en.wikipedia.org/wiki/Subsequence)

Given a string S, your task is to find out how many different subsequence of S is palindrome. Note that for any two subsequence X = <S_{x1}, S_{x2}, ..., S_{xk}> and Y = <S_{y1}, S_{y2}, ..., S_{yk}> , if there exist an integer i (1<=i<=k) such that xi != yi, the subsequence X and Y should be consider different even if S_{xi} = S_{yi}. Also two subsequences with different length should be considered different.

(http://en.wikipedia.org/wiki/Subsequence)

Given a string S, your task is to find out how many different subsequence of S is palindrome. Note that for any two subsequence X = <S

The first line contains only one integer T (T<=50), which is the number of test cases. Each test case contains a string S, the length of S is not greater than 1000 and only contains lowercase letters.

提交代码