Counting Distinct Subsequences

Let $S = S_1S_2\cdots S_N$ be a string. Every string of the form $S_{i_1}S_{i_2}\cdots S_{i_k}$ with $0 \le k \le N$ and $1 \le i_1 < i_2 < \cdots < i_k \le N$ is called a subsequence of $S$. The empty string, of length 0, is also a subsequence of $S$. For example, the string ioi has 7 distinct subsequences: the empty string, i, o, ii, io, oi, and ioi.

Given a string $S$, find the number of distinct subsequences of $S$.

The first line contains the number of test cases $T$ ($1 \le T \le 10\,000$). Each of the next $T$ lines contains one string $S$. $S$ consists only of uppercase English letters, lowercase English letters, and the digits 0 to 9, and its length is between 1 and 1,000 inclusive. Uppercase and lowercase letters are different characters.

For each test case, print the number of distinct subsequences of $S$ on its own line. The empty string is counted. Every input string is guaranteed to have an answer of at most $10^{18}$.