F. Rikka with Nice Counting Striking Back
time limit per test
8 s
memory limit per test
1024 MB
input
standard input
output
standard output

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?

Input

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

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

Example
Input
6
rikkasuggeststoallthecontestants
thisisaproblemdesignedforgrandmasters
ifyoudidnotachievethat
youdbetterskiptheproblem
wishyouahighrank
enjoytheexperience
Output
500
679
244
290
132
163