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.
Input
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$.
Output
For each test case, output the number of prefix-suffix-square free substrings of $s$.
