Square Revolution

Alex loves solving algorithmic problems relating with strings. After solving the problem about counting the number of prefix-square free strings of length at most $n$, he is curious in the number of prefix-suffix-square free substrings of a string $s$. Can you help him?

A string is called a square string if it can be obtained by concatenating two copies of the same string (i.e. $s=uu$ for some word $u$). For example, "abab", "aa" are square strings, while "aaa", "abba" are not. A string is called prefix-suffix-square free if none of its prefixes/suffixes is a square.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains a string $s=s_{1}s_{2}...s_{n}$ $(1 \le n \le 10^5)$ consisting of lowercase English letters.

There are at most $1000$ test cases and the sum of $n$ does not exceed $10^6$.

For each test case, output the number of prefix-suffix-square free substrings of $s$.

4
aaaaa
aabcd
aaabbbccc
kurakujoudo

5
11
12
66

BestCoder Round #87