问题 3444 --又见回文串

3444: 又见回文串

题目描述

  A palindorme is a sequence of one or more characters that reads the same from the left as it does from the right. For example, Z, TOT and MADAM are palindromes, but ADAM is not.
Given a sequence S of N capital latin letters. How many ways can one score out a few symbols (maybe 0) that the rest of sequence become a palidrome. Varints that are only different by an order of scoring out should be considered the same.
给定一个字符串,问有几种删字符的方案使得它变为回文串。
比如ABA,可以删掉B、BA、AB、两个A、不删。

输入

The input file contains several test cases (less than 15). The first line contains an integer T that indicates how many test cases are to follow.
Each of the T lines contains a sequence S (1 ≤ N ≤ 60). So actually each of these lines is a test
多组数据 (小于15)
每组数据的字符串长度不超过60.

输出

每组数一个答案,有多少种不同方法。

样例输入输出

输入#1 复制
3
BAOBAB
AAAA
ABA
输出#1 复制
22
15
5

提示

序号 标题 作者 发表时间 费用 订购数 操作