Vještica

Ο νεαρός ήρωας, ο τυχοδιώκτης Matej, έχει, μετά από ένα μακρύ και επίπονο ταξίδι, φτάσει στον τελικό του προορισμό - το σπίτι της κακιάς μάγισσας Marija. Για να ολοκληρώσει την περιπέτειά του, πρέπει να λύσει το τελευταίο παζλ που του δίνει η μάγισσα.

Για να μπορέσει να λύσει το παζλ της, πρώτα, ο ήρωάς μας πρέπει να εξοικειωθεί με τη δομή δεδομένων που ονομάζεται προθηματικό δέντρο (trie).

Ένα προθηματικό δέντρο είναι μια δομή δεδομένων που αναπαριστά όλα τα προθέματα~^1~ λέξεων από ένα συγκεκριμένο σύνολο με τον ακόλουθο τρόπο:

• Κάθε ακμή του δέντρου συμβολίζεται με ένα γράμμα από το αλφάβητο.
• Η ρίζα του δέντρου αντιπροσωπεύει ένα κενό πρόθημα.
• Όλοι οι άλλοι κόμβοι στο δέντρο αντιπροσωπεύουν ένα μη κενό πρόθημα με τρόπο που κάθε κόμβος αντιπροσωπεύει ένα πρόθημα που προκύπτει από τη σύνδεση γραμμάτων γραμμένων στις ακμές που οδηγούν από τη ρίζα του δέντρου σε αυτόν τον κόμβο (με αυτή τη σειρά).
• Δεν θα υπάρχουν ποτέ δύο ακμές με το ίδιο γράμμα που θα βγαίνουν από έναν μόνο κόμβο (με αυτόν τον τρόπο ελαχιστοποιούμε τον αριθμό των κόμβων που απαιτούνται για την αναπαράσταση όλων των προθημάτων).

Προθηματικό δέντρο για τις λέξεις : "A"", "to", "tea", "ted", "ten", "i", "in", "inn".

Μόνο αφού ο Matej έμαθε τι ήταν το προθηματικό δέντρο αρχίζει το πραγματικό παζλ!

Η μάγισσα, όπως ίσως έχετε μαντέψει, έχει ~N~ λέξεις που αποτελούνται από πεζά γράμματα του αγγλικού αλφαβήτου. Το παζλ θα ήταν πολύ απλό αν η μάγισσα ήθελε να μάθει τον αριθμό των κόμβων του προθηματικού δέντρου για αυτό το σύνολο λέξεων, αλλά δεν την ενδιαφέρει αυτό. Θέλει να γνωρίζει τον ελάχιστο αριθμό κόμβων που μπορεί να έχει ένα προθηματικό δέντρο αφού αλλάξει τα γράμματα κάθε λέξης με αυθαίρετο τρόπο.

Βοηθήστε τον Matej να βρει την απάντηση στο παζλ!

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον ακέραιο αριθμό ~N~ ~(1 \le N \le 16)~.

Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει μια λέξη που αποτελείται από πεζά γράμματα του αγγλικού αλφαβήτου.

Το συνολικό μήκος όλων των λέξεων θα είναι μικρότερο από ~1\,000\,000~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει έναν αριθμό, την απάντηση στο παζλ της μάγισσας Marija.

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

input

3
a
ab
abc

output

4

input

3
a
ab
c

output

4

input

4
baab
abab
aabb
bbaa

output

5

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

Όλες οι λέξεις μπορούν να μετατραπούν στη λέξη "aabb", οπότε το προθηματικό δέντρο θα έχει 5 κόμβους (4 + 1 για τη ρίζα του δέντρου - το κενό πρόθημα).

~^1~Το πρόθημα μιας λέξης είναι μια διαδοχική υποσυστοιχία γραμμάτων από την αρχή της λέξης έως μια συγκεκριμένη θέση στη λέξη.