Rahul has entered into a mysterious land of gems. There is a record S for each of the gems that is maintained in form of a string. Each gem is characterized by some substring of this string. Interestingly, the number of occurrences of a sub-string in S is the exact number of such gems present in the land.
However, Rahul is only interested in unique gems. Please tell the number of such sub-strings that occur exactly once.
Input Format:
The first line of input file contains an integer T, denoting the number of test cases.
Each of the following T lines contain a string.
Output Format:
The output file should contain exactly T numbers, each representing output to corresponding test case.
Constraints:
1 ≤ T ≤ 10
1 ≤ |S| ≤ 105
Each of the characters in string S lie between a-z.
Sample Explanation:
Case #1:
aaa is the only substring that occurs once.
Case #2:
b, ab, ba, aba are the unique substrings.
Case #3:
aba, bab, ba, and abab are unique substrings.
