Hasinur didn't Know how to count number of distinct sub-strings of a given string. That is why he didn't find any love in his life before. Every girl he proposed to rejected him right away. Then he learned how to count number of distinct sub-strings of a string. Now he has too many loves in his life. So if you know how to count number of distinct sub-strings of a string then you will find love too.

In this problem, you will be given several test cases. In each test case, you will be given a string. You will have to find the number of distinct sub-strings of that string.

Input

Input will start with an integer T (1 ≤ T ≤ 100), number of test cases. In each test case a string will be given. The length of each string will be 50 at max. A string will contain only lowercase Latin letters ('a' - 'z').

Output

For each test case, output an integer in a single line—the answer of the corresponding test case according to the problem statement.

Sample

Input	Output
2 aaaa aaa	4 3

A substring is a contiguous sequence of characters within a string. For example; the sub-strings of the string "abc" are "a", "ab", "abc", "b", "bc" and "c".