National Olympiad in Informatics, China, 2014
Recently, the zookeeper noticed that number of all-eat and no-work animals have been increasing. Take penguins for example – they only care about getting food from the zoo's visitors through showing off their cuteness alone. To fix the bad vibe around the zoo and to ensure that animals only get food via exhibiting their true talents, the zookeeper has decided to set up an algorithms class to teach algorithms to the animals.
One day, the zookeeper decided to lecture the KMP algorithm to the animals.
Zookeeper: "For a given string of length , we can construct an array in running time . Can anybody guess the meaning of ?
Panda: "Within the first characters of string , the length of the longest substring (excluding itself) that is both its prefix and suffix will be stored in ."
Zookeeper: "Very good! Can you give an example?"
abcababc, then . This is because the first
5 characters is
ab is both its prefix and suffix, and a
longer substring with this property does not exist. Likewise, we can
find that , ,
, and ."
The zookeeper commended Panda's studiousness. Then, he carefully explained how could be computed in .
Before dismissing the class, the zookeeper posed a problem: "The KMP
algorithm can only generate the array . We wish to obtain an even
more powerful array – within the first characters of string
, the number of substrings that is both its prefix and suffix, and
that the prefix and suffix does not overlap, will be stored in
. For example, if
aaaaa, then . This is
because for the first 4 characters of ,
aa each satisfy the conditions of 'being both a prefix and suffix,' as
well as guaranteeing that the prefix and suffix do not overlap. Although
aaa does satisfy the condition of 'being both a prefix and
suffix,' we cannot count it because as simultaneously a prefix and
aaaa, it overlaps with itself. By the same reasoning, we can
see that , , and ."
Finally, the zookeeper designated a prize. The first student to solve this will be rewarded a box of chocolates. After hearing this, Penguin, who has been sleeping for the entire class, has immediately awoken! But Penguin doesn't have a clue how to solve this problem. So, he has scoured the entire zoo to find you for help. Can you help Penguin write a program to compute the array?
Specifically, to avoid huge amounts of output, you do not have to output each value of . Instead, you will only have to output . Here, .
The first line of input contains a single integer , representing the
number of test cases.
For the next lines, each line will describe one instance of the problem. Each instance will consist of the single string . It is guaranteed that will only consist of lowercase letters.
The input will not contain extra or trailing spaces.
The output should contain lines, with each line being the answer to the corresponding input string. The order of the answers should be the same as the order of the strings in the input. For each string, the answer should be a single integer representing the answer modulo .
3 aaaaa ab abcababc
36 1 32
The constraints of all the test cases are outlined below.