{"raw_statement":[{"iden":"statement","content":"As we know, Yuta is poor at counting numbers. Rikka is worrying about this situation, so she gives Yuta some counting tasks to practice. Here is one of them:\n\nIn computer programming, a string is traditionally a sequence of characters and a substring of a string is a contiguous sequence of characters within the string. For instance, _snowball_ is a string, _now_ is a substring of _snowball_ and _bow_ is not a substring of _snowball_. Moreover, the concatenation of two strings $U$ and $V$ is named as $U V$, that is, if $U$ is _snow_ and $V$ is _ball_, then $U V$ is _snowball_.\n\nRikka has a string $S$ of length $n$ and she wants Yuta to count how many distinct _nice_ strings in total. Here, she calls a non-empty string $T$ _nice_ if\n\nIt is too difficult for Yuta. Can you help him?\n\nThe input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 1000$), the number of test cases.\n\nFor each test case, the only line contains a single string $S$ of length $n$ ($1 <= n <= 2 times 10^5$) with only lowercase letters.\n\nThe input guarantees that the sum of $n$ in all test cases is at most $5 times 10^6$.\n\nFor each test case, output a single line with a single integer, the answer.\n\n"},{"iden":"input","content":"The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 1000$), the number of test cases.For each test case, the only line contains a single string $S$ of length $n$ ($1 <= n <= 2 times 10^5$) with only lowercase letters.The input guarantees that the sum of $n$ in all test cases is at most $5 times 10^6$."},{"iden":"output","content":"For each test case, output a single line with a single integer, the answer."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ S $ be a string of length $ n $ over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ \\mathcal{U}(S) $ denote the set of all non-empty substrings of $ S $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. For each test case: $ 1 \\le n \\le 2 \\times 10^5 $  \n3. $ \\sum_{\\text{all test cases}} n \\le 5 \\times 10^6 $  \n\n**Objective**  \nCompute $ \\left| \\mathcal{U}(S) \\right| $, the number of distinct non-empty substrings of $ S $.","simple_statement":"Count the number of distinct non-empty substrings in a given string.","has_page_source":false}