Ekoeko

Πρέπει να γνωρίζετε την ιστορία ενός εξωγήινου που ονομάζεται Eko Eko, ο οποίος πήρε το όνομά του λόγω μιας δυσλειτουργίας της μεταφραστικής του συσκευής. Ο μικρός εξωγήινος είναι για άλλη μια φορά στη Γη για να βοηθήσει τους γήινους να καθαρίσουν μετά το πέρας των Χριστουγέννων. Ωστόσο, η μεταφραστική συσκευή του Eko Eko σταμάτησε να λειτουργεί ξανά.

Αυτή τη φορά, η συσκευή όχι μόνο επαναλαμβάνει μια λέξη, αλλά αλλάζει και τη σειρά των γραμμάτων σε μια λέξη. Για παράδειγμα, η λέξη "slon" γίνεται πρώτα "slonslon" και στη συνέχεια αλλάζοντας τη σειρά των γραμμάτων θα μπορούσε να γίνει "slosnoln" ή "soolnlsn" κ.λπ. Η ποσότητα χρυσού που απαιτείται για την επισκευή της συσκευής του Eoo Kek εξαρτάται από τον αριθμό των απαιτούμενων εναλλαγών των παρακείμενων χαρακτήρων, ώστε να μεταφραστεί η κακώς μεταφρασμένη λέξη του Kok Oee σε μια λέξη που αποτελείται από μία επανάληψη.

Για παράδειγμα, εάν η συσκευή του Keo Koe μεταφράζει μια λέξη σε "soolnlsn", αρκεί να γίνουν τέσσερις εναλλαγές γειτονικών χαρακτήρων για να ληφθεί μια λέξη που δημιουργείται από μια επανάληψη - "olsnolsn" (δείτε τη διευκρίνιση του τρίτου παραδείγματος), οπότε τέσσερα κομμάτια χρυσού αρκούν για να επισκευάσει τη συσκευή του. Παρατηρήστε ότι η λέξη που προκύπτει από μια ακολουθία τέτοιων εναλλαγών δεν είναι απαραίτητα η λέξη που ήθελε αρχικά να πει ο Koo Kee. Αυτό δεν επηρεάζει την ποσότητα χρυσού που απαιτείται για την επισκευή της συσκευής του.

Θα θέλατε να βοηθήσετε τον Eke Koo, αλλά αν κλέψετε μεγάλη ποσότητα κοσμημάτων από τη μητέρα σας, δεν θα πάρετε χριστουγεννιάτικο δώρο. Αυτός είναι ο λόγος για τον οποίο για μια δεδομένη λέξη που προέκυψε από τη συσκευή μετάφρασης του Keo Koe, θέλετε να προσδιορίσετε τον ελάχιστο δυνατό αριθμό εναλλαγών των παρακείμενων χαρακτήρων για να λάβετε μια λέξη που αποτελείται από μία επανάληψη.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο αριθμό ~n~ - το μήκος της λέξης που προσπαθεί να πει ο Eek Ook.

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

Έξοδος

Στη μοναδική γραμμή εκτυπώστε τον ελάχιστο δυνατό αριθμό εναλλαγών των παρακείμενων χαρακτήρων για να μετατρέψετε τη λέξη του Keo Koe σε λέξη μονής επανάληψης.

Βαθμολογία

Οι περιορισμοί για το ~n~ είναι ~1 \le n \le 100\,000~ για κάθε υποπρόβλημα.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	10	Η συμβολοσειρά αποτελείται από ~n~ εμφανίσεις του ~a~ και στη συνέχεια ~n~ εμφανίσεις του ~b~.
2	20	Κάθε γράμμα εμφανίζεται το πολύ δύο φορές.
3	20	Τα πρώτα ~n~ καθώς και τα τελευταία ~n~ γράμματα είναι ίδια, αλλά πιθανώς με διαφορετική σειρά.
4	20	~1 \le n \le 1000~
5	40	Χωρίς πρόσθετους περιορισμούς.

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

input

3
koeeok

output

3

input

3
kekoeo

output

1

input

4
soolnlsn

output

4

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

Ένας τρόπος για να μεταβείτε από το "soolnlsn" σε μια λέξη μίας επανάληψης, χρησιμοποιώντας τέσσερις εναλλαγές είναι:

$$\displaystyle soolnlsn \rightarrow so\underline{lo}nlsn \rightarrow sol\underline{no}lsn \rightarrow \underline{os}lnolsn \rightarrow o\underline{ls}nolsn$$