Problem D: Necklace!

Problem D: Necklace!

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 1030  Solved: 357
[Submit][Status][Web Board]


D1rtyPaw5 wants to drink coco with his girlfriend! Unfortunately, he has no girlfriend now, but he still wishes to prepare a necklace for his future goddess.  

This is a kind of special necklace which contains a sequence of diamonds with letters in, and it can be regarded as a string. D1rtyPaw5 gives Amayama a semi-finished necklace and askes Amayama to add as few as possible diamonds to the head or tail of the necklace to make the necklace consist of at least two same circulation sections. A circulation section of a string is a substring which could build the original string by repeating the circulation section several times.  

Please answer the number of diamonds that Amayama should add.


The first line contains an integer n, which is the number of test cases. (1<=n<=1000) 

For each case, there is only one line of string containing lowercase letters, which indicates the semi-finished necklace.  The length of each string is no more than 200000.


The output for each test case is an integer which is the number of diamonds that Amayama should add.

Sample Input


Sample Output



If a necklace has contained two circulation sections and ended with an uncomplete circulation section, you should complete this section to finish the whole necklace.