题目描述

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?

输入格式

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

输出格式

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