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.

Constraints:

1<=T<=50

Length of the string S is between 1 and 1000000 characters.

S may contain any ascii character other than space.

Sample Input:
4
abcabcabcab
babaaba
bacbacbacba
babab

Sample Output:
3
5
3
2

Caution: Large IO.
Use efficient IO like scanf instead of cin.

Problem Setter: Dhruva Bhaswar

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0