Savez

Υπάρχουν οκτώ πλανήτες και ένας πλανητοειδής στο ηλιακό σύστημα. Δεν είναι γνωστό ότι υπάρχει ένας μυστικός πλανήτης ~S4~ που κατοικείται από μικρά πλάσματα παρόμοια με τις αρκούδες, με την κωδική τους ονομασία να είναι Lodas. Αν και αυτό το γεγονός είναι καλά κρυμμένο από το κοινό, η ένωση Savez έστειλε μια ομάδα με επικεφαλής τον στρατηγό Henrik για να μελετήσει τα Lodas. Ανακαλύφθηκε ότι τα Lodas έχουν την ικανότητα τηλεμεταφοράς και θέλει να τα προσλάβει στον στρατό του.

Το ένα Lod αποτελείται από ~N~ συμβολοσειρές όπου η ~i~-οστή συμβολοσειρά συμβολίζεται με ~x_i~ . Η έρευνα έχει δείξει ότι ο αριθμός των τηλεμεταφορών που μπορεί να κάνει ένα Loda εξαρτάται από μια ειδική υποακολουθία (όχι απαραίτητα διαδοχική) αυτών των χορδών. Οι συμβολοσειρές ~x_i~ και ~x_j\;(i < j)~ μπορούν και οι δύο να βρίσκονται σε αυτήν την ακολουθία εάν και μόνο εάν η συμβολοσειρά ~x_j~ αρχίζει και τελειώνει με τη συμβολοσειρά ~x_i~. Ο αριθμός των τηλεμεταφορών που μπορεί να κάνει ένα Loda είναι το μήκος της μεγαλύτερης περιγραφόμενης υποακολουθίας.

Προσδιορίστε τον αριθμό των τηλεμεταφορών.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο ~N~, τον αριθμό των συμβολοσειρών. Κάθε μία από τις ακόλουθες \(Ν\) γραμμές περιέχει μια συμβολοσειρά που αποτελείται από κεφαλαία γράμματα του αγγλικού αλφαβήτου. Τα δεδομένα εισόδου θα είναι τέτοια που θα υπάρχουν λιγότεροι από δύο εκατομμύρια χαρακτήρες συνολικά.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον αριθμό των τηλεμεταφορών που μπορεί να κάνει ένα Loda.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 40% των συνολικών πόντων, θα ισχύει ~(1 \leq N \leq 500)~.

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

input

5
A
B
AA
BBB
AAA

output

3

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

Το πρόθεμα και επίθημα μπορούν να τέμνονται, έτσι η υποακολουθία είναι ~A \rightarrow AA \rightarrow AAA~

input

5
A
ABA
BBB
ABABA
AAAAAB

output

3

input

6
A
B
A
B
A
B

output

3

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

Οι συμβολοσειρές στην υποακολουθία επιτρέπεται να είναι ίσες, επομένως η υποακολουθία είναι ~A \rightarrow A \rightarrow A\;~ ή ~B \rightarrow B \rightarrow B~