A string is considered good if it can be written in the form AABB with A and B being non-empty strings. For example, the string ababaa is a good string because it can be formed by taking A=ab and B=a. A and B can be equal.
Given a string S, count the number of consecutive substrings of S that are good strings.
### Input
- The first line contains an integer T, the number of strings to process.
- The next T lines each contain a string S corresponding to a test case.
### Output
- For each string, print an integer, the answer.
### Example
Input:
4aabaabaabaabaaaabaababaaba
Output:
3547
### Constraints
In each test case:
- 1≤T≤10,1≤n≤30000.