If a string can be written in the form of where and are arbitrary non-empty strings, then we say this is a good partition. For example, it is possible to write the string in the form of by letting and .
Some strings do not admit a good partition, while some strings admit multiple good partitions. For example, for the above string , it is also possible to write it in the form of by letting and . The string does not admit good partitions.
Given a string of length , compute the sum, over all its substrings, of the number of good partitions of those substrings. Here, substring refers to a contiguous part of the string.
Please pay attention to the following details:
- The same string appearing at different locations are considered distinct. All good partitions corresponding to the same string should count towards the answer.
- It is possible to have in a good partition. For example, the string admits good partition .
- The string itself is one of its substrings.
Input Specification
Each input file has several test cases.
The first line of the input file contains one integer denoting the number of test cases in the file.
In the following lines, each line contains a string consisting of lower-case English letters.
Output Specification
Output lines: each line consists of an integer denoting the total number of good partitions among all possible partitions of substrings of .
Sample Input 1
4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba
Sample Output 1
3
5
4
7
Explanation for Sample 1
Let denote the substring of consisting of the -th character to the -th character of , with index starting from .
In the first test case, there are three substrings admitting good partitions: with , with , and with . Other substrings of do not admit good partitions, so the answer shall be .
In the second test case, admit good partition , so the total contribution to the final answer is . For string , it admits two good partitions ( or ). The different good partitions corresponding to the same substring should all count towards the final answer, so the final answer to the second test case is .
In the third test case, and admit two good partitions respectively. is the example described in the problem description. The answer should be .
In the fourth test case, each of admits one good partition, and admits two good partitions, so the answer should be .
Attachment Package
The samples are available here.
Sample 2
See ex_excellent2.in
and ex_excellent2.ans
.
Sample 3
See ex_excellent3.in
and ex_excellent3.ans
.
Constraints
For all test cases, , .
Test case | Special properties | |
---|---|---|
1,2 | All characters of are same. | |
3,4 | ||
5,6 | No additional constraints. | |
7,8 | ||
9,10 | ||
11,12 | ||
13,14 | ||
15 | ||
16 | ||
17 | ||
18 | ||
19 | ||
20 |
Comments