Hasinur’s love interest is always curious about different strings and their properties. He wants to impress her and needs your help.

You will be given several strings and 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 at most 50. 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".