Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T ≤ 20;
Each test case consists of one string, whose length is ≤ 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Input:
2
CCCCC
ABABA
Output:
5
9

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.