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.

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.