Given a string S, Dexter wants to find the number of different substrings in S. He considers two substrings same if they have a cyclic permutation which is same. If T = T1T2T3 . . . Tn is a string of length n then it has n cyclic permutations and they are TiTi+1 . . . TnT1T2 . . . Ti−1 for all 1 ≤ i ≤ n. (Note that, Tn+1 and T0 are non-existing). For example, if T = “abcd” there are 4 cyclic permutations and they are: “abcd”, “bcda”, “cdab” and “dabc”. So, string “aba”, “aab” and “baa” are all considered same. But “abc” and “bac” are different as there is no cyclic permutation of them which are same. Input First line contains an integer T (T ≤ 50) denoting the number of test cases. Each of the next T lines contains a string S which is composed of only lowercase latin letters. You can assume that the length of S is between 1 and 200 inclusive. Output For each test case, output the number of different substrings in a line. Explanation: If S = “abcba” there are 10 cyclic different substrings and they are: “a”, “b”, “c”, “ab”, “bc”, “abc”, “bcb”, “cba”, “abcb” and “abcba”. Sample Input 3 abcba aab zzxzz Sample Output 10 5 7