Distinct Substrings and Minimal DFA States

You are given n strings composed of lowercase letters: \(s_1, s_2, \ldots, s_n\). Your task is two‐fold:

1. Count the number of distinct non-empty substrings among all the given strings.
2. Let \(Q\) be the minimal DFA that accepts all suffixes of \(s_1, s_2, \dots, s_n\) (in other words, the generalized suffix automaton built from these strings). Output the number of states (nodes) in \(Q\).

Note: If the above wording is confusing, you only need to output the number of nodes in the generalized suffix automaton constructed from the input strings.

inputFormat

The input consists of multiple lines. The first line contains an integer \(n\) indicating the number of strings. The following \(n\) lines each contain a non-empty string consisting of lowercase letters.

n
s_1
s_2
\(\.\.\.\)
s_n

outputFormat

Output a single integer, the number of states in the generalized suffix automaton built from all input strings.

result

sample

1
abc

4