Given $n$ strings $s_1, s_2, \dots, s_n$ consisting of lowercase letters, find the number of distinct substrings. (Excluding the empty string.)

Input

The first line contains a positive integer $n$.

The following $n$ lines each contain a string, where the $i$-th line represents the string $s_i$.

Output

A single line containing a positive integer representing the answer.

Examples

Input 1

10
orzhy
hyakcts
hyakapio
hyakioi
hyaknoi
hyaknoip
bytheway
therulesforthenextseasonwillbeadjustedsoonsostaytuned
gpofuralswillbeheldonmaytheninethusualtimeuralchampionshiponsiteteamsresultswillbecounted
thewidesiberianolympiadchangedtherulesfortheselectioncontestfromacmtomixedacmmarathonwithvariablescoringsoitcannotbeusedastheopencupstageatthecurrentseasoninnextseasonsthenonacmscoringstagesmaybeconsideredbutmajorlastminutechangesarenotacceptablesothegrandprixofeurasiaatoctthetenthiscancelled

Output 1

47675

Subtasks

For all test cases, $1 \leq n \leq 10^5$ and $1 \leq \sum |S| \leq 10^6$.