Size of the Dictionary

Time limit2sMemory limit128 MB

Summary
Count distinct words formed as base words themselves, plus prefix-of-one-base-word concatenated with suffix-of-another-base-word combinations.
Level

Medium7 of 10

Topics
Trie, String matching, Hash map
Solved
No attempts yet

Problem

Jungyu wants to invent a new language called Jomal. First, Jungyu writes down a list of all the words that form the foundation of Jomal. Each word on this list is called a base word.

Using the base words, Jungyu now builds new words to complete the Grand Jomal Dictionary. A word appears in the Grand Jomal Dictionary if it satisfies at least one of the following conditions.

  • The word itself is a base word.
  • The word can be split into two parts so that the front part is a prefix of some base word (the whole word counts as a prefix) and the back part is a suffix of some base word (the whole word counts as a suffix). Both parts must be non-empty.

Determine how many distinct words the Grand Jomal Dictionary contains under this rule.

Input

The first line contains the number of base words n (1 ≤ n ≤ 10 000). Each of the next n lines contains one base word. Every base word consists only of lowercase letters and has length between 1 and 40, inclusive.

Jungyu is lazy and did not check whether the list contains duplicate words, so the same word may appear several times; identical words are treated as one.

Output

Print, on a single line, the number of distinct words in the Grand Jomal Dictionary.

Examples10

  1. Example 1

    Input
    3
abc
def
abef
    Expected output
    60

  2. Example 2

    Input
    1
a
    Expected output
    2

  3. Example 3

    Input
    1
ab
    Expected output
    4

  4. Example 4

    Input
    3
abc
abc
abc
    Expected output
    8

  5. Example 5

    Input
    2
a
b
    Expected output
    6

  6. Example 6

    Input
    2
a
bc
    Expected output
    10

  7. Example 7

    Input
    3
a
a
a
    Expected output
    2

  8. Example 8

    Input
    2
ab
ba
    Expected output
    14

  9. Example 9

    Input
    3
ab
abc
abcd
    Expected output
    33

  10. Example 10

    Input
    26
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
    Expected output
    702