A perfect cyclic string is a string which can be represented as the repeated concatenation of one of its substrings. In fact, all strings can be formed in such way, and perhaps with more than one possible substring; substrings also can be the original string itself. For example: The string “cdabcdabcdab” can be formed with the substring “cdab”. The string “abababab” can be formed with the substrings “ab” or “abab”, or even “abababab”. And the string “qwertyuiop” can be formed only with the substring “qwertyuiop” (the string itself). Given some string, you must find the size of the minimum substring which can be used to form the original given string. Input The first line contains an integer number T not greater than 103 representing the amount of strings to process. Each of the following T lines contains a string for processing of at most 103 lowercase letters of the English alphabet. You can safely assume that the sum of lengths of all given strings do not exceed 5·105. Output For each input string you must print an integer number with an end of line, representing the size of the minimum substring which can be used to form the original given string. Sample Input 5 aaaa abababab cdabcdabcdab qwertyuiopasdfg abcabcabcabcxabcabcabcabx Sample Output 1 2 4 15 25