Problem E
Shakespeare, who?

You would like to write a very special poem for your friend. You know a list of $n$ words that your friend likes. We will call these words beautiful words. You want every line of your poem to begin and end with a beautiful word. Any given line must use the same beautiful word at the beginning and end of the line, but different lines can use different beautiful words. You do not care about the other words in any line (just the first and last!).

Your friend thinks your poem is beautiful every time some prefix of the first word in a line matches a suffix of the last word of the previous line. Further, your friend hates it if they see the same beautiful word in two consecutive lines, or if the first word of a line and the last word of the previous line share no common prefix/suffix. So you will ensure that your poem doesn’t have such lines.

More precisely, you can define the Shakespearian index of a line $i$ ($i\geq 2$) to be the length of the longest prefix of the first word of line $i$ that is also a suffix of the last word of line $i-1$. The Shakespearian index of the first line will always be $0$. The beauty of the poem is defined as the sum of the Shakespearian indexes of all the lines in the poem.

What is the most beautiful poem you can write?

Input

The first line of the input contains a single integer $n$, ($1\leq n \leq 500$).

The next $n$ lines each contain a distinct beautiful string, which is a word that only contains lowercase English letters a-z. The length of each beautiful string is at most $2000$.

Output

Print a single integer that is the beauty value of the most beautiful poem you can write. If you can write an infinitely beautiful poem, print “Shakespeare, who?”.

Sample Explanation

For the first sample, one possible maximally beautiful poem (ignore punctuation) is
elephant, oh mighty elephant,
anteater, oh hungry anteater,
raccoon, oh poor raccoon!

3
raccoon
elephant
anteater

4

2
tractor
torrent

Shakespeare, who?