Powerful Literature (CANNOT BE SOLVED IN PYTHON, USE CPP)

As the latest magician at the Royal School of Prestidigitation (RSP), you need to record a list of spells in your spellbook.

Your spellbook remembers the spells you write. Each time you write a spell, it gains power equal to the length of all prefixes it shares with all existing spells.

For example, if you write spells "ABC", "ACD", "ACDE" and "AB" in the spellbook, then:

• When you write "ABC", the book gains 0 power. No other spells exist yet.
• When you write "ACD", the book gains 1 power. With ACD, ABC shares a prefix of length 1.
• When you write "ACDE", the book gains 4 power. With ACDE, ABC shares a prefix of length 1, ACD shares a prefix of length 3.
• When you write "AB", the book gains 4 power. With AB, ABC, shares a prefix of length 2; ACD and ACDE each share a prefix of length 1.

Overall, the book gains 0 + 1 + 4 + 4 = 9 power.

Given a list of spells, how much power will the spellbook gain?

Input

The first line consists of an integer ~N~ ~(1 \leq N \leq 1500)~, the number of spells you will record.

The next ~N~ lines consist of strings ~S_i~, the ith spell, to write in your spellbook. Each spell consists of uppercase English letters and is between ~1~ and ~1000~ characters long.

Output

Output the amount of power the spellbook will gain after writing down all of the spells.

Example

Input

5
RAVISSTUDYPROGRAM
RAVIISVERYCOOL
RAVEL
TOMFREW
RAVE

Output

20

• When you write "RAVISSTUDYPROGRAM", the book gains 0 power. No other spells exist yet.
• When you write "RAVIISVERYCOOL", the book gains 4 power. RAVISSTUDYPROGRAM shares a prefix of length 4.
• When you write "RAVEL", the book gains 6 power. RAVISSTUDYPROGRAM AND RAVIISCOOL each share a prefix of length 3.
• Whne you write "TOMFREW", the book gains 0 power, as "TOMFREW" does not share a prefix with any previous spells.
• When you write "RAVE", the book gains 10 power. RAVISSTUDYPROGRAM AND RAVIISCOOL each share a prefix of length 3, and RAVEL shares a prefix of length 4.

All together, the book gains 0 + 4 + 6 + 0 + 10 = 20 power.