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| ≤ 10⁵
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.