Rima

Ο μικρός Adrian είναι λάτρης της ομοιοκαταληξίας. Πιστεύει ότι δύο λέξεις έχουν ομοιοκαταληξία εάν και μόνο αν η μεγαλύτερη κοινή τους κατάληξη είναι όσο η μεγαλύτερη από τις δύο λέξεις ή μικρότερη από τη μεγαλύτερη λέξη κατά 1. Με άλλα λόγια, το ~A~ και το ~B~ έχουν ομοιοκαταληξία αν και μόνο αν ισχύει ~MKY(A,\;B) \le max(|A|,\;|B|) - 1~ (Μεγαλύτερη Κοινή Υπακολουθία).

Μια μέρα, ενώ διάβαζε μια συλλογή διηγημάτων, αποφάσισε να συνθέσει τη μεγαλύτερη δυνατή ακολουθία λέξεων έτσι ώστε κάθε δύο διαδοχικές λέξεις να ομοιοκαταληκτούν. Κάθε λέξη από την ακολουθία μπορεί να εμφανιστεί μόνο μία φορά.

Ο Adrian έχει κουραστεί από αυτήν την εργασία, γι' αυτό αποφάσισε να επιστρέψει στο διάβασμα και σας ζητά να λύσετε αυτό το πρόβλημα αντί για εκείνον.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N\;(1 \le N \le 500\,000)~.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει μία λέξη που αποτελείται από πεζά γράμματα του αγγλικού αλφαβήτου. Όλες οι λέξεις είναι διαφορετικές μεταξύ τους και το συνολικό τους μήκος είναι το πολύ ~3\,000\,000~.

Έξοδος

Πρέπει να τυπώσετε το μήκος της μεγαλύτερης ακολουθίας.

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των πόντων, θα ισχύει ~N \le 18~.

Παραδείγματα

input

4
honi
toni
oni
ovi

output

3

input

5
ask
psk
krafna
sk
k

output

4

Επεξήγηση του 2ου παραδείγματος:

Η μόνη δυνατή ακολουθία είναι ask-psk-sk-k.

input

5
pas
kompas
stas
s
nemarime

output

1

Επεξήγηση του 3ου παραδείγματος:

Δεν υπάρχουν δύο λέξεις με ομοιοκαταληξία.