409477: GYM103577 C Corona

Özlem is researching variants of the covid-19 virus. She has figured out a way to measure how transmissible a variant is by analyzing its genome sequence. In general, any genome sequence is highly transmissible if it has a large prefix which is also its own suffix. For example: for GACTCGA, GA is the longest prefix which is also a suffix (note that the full string is not a valid prefix/suffix). They call the $$$level$$$ of a sequence the length of the longest prefix which is also a suffix, so the level of GACTCGA is $$$2$$$. Covid-19 is a very special virus, so its transmissibility is equivalent to the sum of all substrings' level.

Özlem has asked you to compute the transmissibility for several genome sequences of variants collected all around the world. There is a lot of variants out there, so you need to develop a solution that is very fast so that Özlem and you can analyze variants in real-time.

There will be several genome sequences (at most $$$50$$$), one on each line. Each sequence is a string consisting of lower-case letters only. The length of each sequence is at most $$$5000$$$.

For each sequence, print its transmissibility on a different line.

agcagct
tomi
acmicpc
universidadnacional
yvanehtnioj

10
0
3
12
1