A character string is said to have period \textbf{k} if it can be formed by concatenating one or more repetitions of another string of length \textbf{k}. For example, the string "\textbf{abcabcabcabc}" has period \textbf{3}, since it is formed by \textbf{4} repetitions of the string "\textbf{abc}". It also has periods \textbf{6} (two repetitions of "\textbf{abcabc}") and \textbf{12} (one repetition of "\textbf{abcabcabcabc}"). Write a program to read a character string and determine its smallest period. \InputFile The first line oif the input file will contain a single integer N indicating how many test case that your program will test followed by a blank line. Each test case will contain a single character string of up to \textbf{80} non-blank characters. \OutputFile An integer denoting the smallest period of the input string for each input. Two consecutive output are separated by a blank line.