BGC TRUST IUPC 2012

Problem A

Distinct Substring

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 is a string of length n then it has n cyclic permutations and they are  for all . (Note that,  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.

Sample Input	Output for Sample Input
3 abcba aab zzxzz	10 5 7

Explanation: If S = “abcba” there are 10 cyclic different substrings and they are: “a”, “b”, “c”, “ab”, “bc”, “abc”, “bcb”, “cba”, “abcb” and “abcba”.

Problemsetter: Tasnim Imran Sunny

Special Thanks: Kazi Rakibul Hasan