405616: GYM102012 F Rikka with Nice Counting Striking Back

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, snowball is a string, now is a substring of snowball and bow is not a substring of snowball. Moreover, the concatenation of two strings $$$U$$$ and $$$V$$$ is named as $$$U V$$$, that is, if $$$U$$$ is snow and $$$V$$$ is ball, then $$$U V$$$ is snowball.

Rikka has a string $$$S$$$ of length $$$n$$$ and she wants Yuta to count how many distinct nice strings in total. Here, she calls a non-empty string $$$T$$$ 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