Good string - MarisaOJ: Marisa Online Judge

Good string

Time limit: 1000 ms
Memory limit: 256 MB
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=\text{ab}$ and $B=\text{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: ``` 4 aabbbb cccccc aabaabaabaa bbaabaababaaba ``` Output: ``` 3 5 4 7 ``` ### Constraints In each test case: - $1 \le T \le 10, 1 \le n \le 30000$.
Test $n\le$ Special condition
1,2 300 All characters in $S$ are similar
3,4 2000
5,6 10 None
7,8 20
9,10 30
11,12 50
13,14 100
15 200
16 300
17 500
18 1000
19 2000
20 30000