# Square Revolution

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

## Description

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$.

## Sample Input

4
aaaaa
aabcd
aaabbbccc
kurakujoudo

## Sample Output

5
11
12
66

wange2014

## Source

BestCoder Round #87