Count Distinct Substrings

You are provided with a string S. Your task is to determine and return the number of distinct substrings, including the empty substring, of this given string. Implement the solution using a trie data structure.

Input:

First line contains an integer T representing the number of test cases. 
For each test case, a single line contains the string S.

Output:

Output consists of T lines, each containing an integer result for each test case, representing the number of distinct substrings of string S.

Example:

Input:

2
ab
abc

Output:

4
7

Explanation:

For 'ab', distinct substrings are: "", "a", "b", "ab".
For 'abc', distinct substrings are: "", "a", "b", "c", "ab", "bc", "abc".

Constraints:

• 1 <= T <= 5
• 1 <= |S| <= 10^3
• S consists only of lowercase English letters.

Note:

No need to handle printing; this has been managed already. Focus purely on implementing the specified function.