Sheh ! You are bored again. :P
You guys decide to play a game, this time based on your names. All of you write your name on a sheet of paper and the one whose name has the maximum number of distinct substrings of his name wins the game.
But counting this is a tiresome task, isn't it ?
So, you think about writing a clever piece of code for doing this and finding out the winner amongst you.
The winner takes it all.
You are given a string and you have to find the number of distinct substrings of that string.

Input
The first line of input contains a single integer T denoting the number of test cases.
Then T lines follow.
Each line is a string of length <=100

Output
For each test case, output the number of distinct substrings on a single line.

Constraints
Length of strings<=100

Example
Input:
2
CCCCC
ABABA

Output:
5
9

Explanation
Example case 2. Explanation for the testcase with string ABABA:
len=1 : A,B
len=2 : AB,BA
len=3 : ABA,BAB
len=4 : ABAB,BABA
len=5 : ABABA
Thus, total number of distinct substrings is 9.

见题面

见题面