Problem Description

As we know, Yuta is poor at counting numbers. Rikka is worrying about this situation, so she gives Yuta some counting tasks to practice. Here is one of them:

In computer programming, a string is traditionally a sequence of characters and a substring of a string is a contiguous sequence of characters within the string. For instance, $\text{snowball}$ is a string, $\text{now}$ is a substring of $\text{snowball}$ and $\text{bow}$ is not a substring of $\text{snowball}$. Moreover, the concatenation of two strings $U$ and $V$ is named as $U V$, that is, if $U$ is $\text{snow}$ and $V$ is $\text{ball}$, then $U V$ is $\text{snowball}$.

Rikka has a string $S$ of length $n$ and she wants Yuta to count how many distinct $\textit{nice}$ strings in total. Here, she calls a non-empty string $T$ $\textit{nice}$ if

• $T$ is a substring of $S$; and
• $T P$ is not a substring of $S$ for any non-empty string $P$ meeting the condition that $T P$ and $P T$ are the same string.

It is too difficult for Yuta. Can you help him?

Input Format

The input contains several test cases, and the first line contains a single integer $T$ ($1 \le T \le 1000$), the number of test cases.

For each test case, the only line contains a single string $S$ of length $n$ ($1 \le n \le 2 \times 10^5$) with only lowercase letters.

The input guarantees that the sum of $n$ in all test cases is at most $5 \times 10^6$.

Output Format

For each test case, output a single line with a single integer, the answer.

6
rikkasuggeststoallthecontestants
thisisaproblemdesignedforgrandmasters
ifyoudidnotachievethat
youdbetterskiptheproblem
wishyouahighrank
enjoytheexperience

500
679
244
290
132
163