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.
n=input()
for i in range(n):
	inp=raw_input()
	li=[]
	for j in range(len(inp)):
		string=inp[j]
		li.append(string)
		for k in range(j+1,len(inp)):
			string+=inp[k]
			li.append(string)
	print len(set(li))