Minimum Length Message
Arjun had to urgently leave for a wedding ceremony. While he was waiting at bus station, he was constantly looking at an LED display. The LED board displayed a moving message repeating again and again.
The characters appeared on one side, rolled to the other and finally disappeared. Arjun, the programming prodigy in BIT Mesra, got curious about the length of the message. He carefully observed the sign for some period of time and wrote down the letters that he saw in order.
As his bus is to come very soon, he didn't get the time to determine the minimum possible length of the message. So, he needs your help.
For example, if he saw the letters "abcabcabcab", the possible messages would be "bca" and "abcabc". The shortest possible length in this case would be 3.
So, in this problem you people would be given a string S, the sequence of letters that Arjun observed flashing across the electronic sign. You have to print the minimum possible message length that could have produced the given string S. There are T test cases and you have to print the answer for each on a single line.
Length of the string S is between 1 and 1000000 characters.
S may contain any ascii character other than space.
Caution: Large IO.
Use efficient IO like scanf instead of cin.
Problem Setter: Dhruva Bhaswar