Palinilap

Το παλίνδρομο είναι μια λέξη που διαβάζεται το ίδιο προς τα πίσω με τα εμπρός. Για παράδειγμα, "a", "abba" και το "anavolimilovana" είναι παλίνδρομα. Ένα δείγμα είναι μια συμβολοσειρά ενός ή περισσότερων πεζών γραμμάτων του αγγλικού αλφάβητου, και το βάρος ενός δείγματος είναι ο αριθμός των υποσυμβολοσειρών (λέξεων) του που είναι παλίνδρομες, μετρώντας κάθε λέξη ξεχωριστά.
Πιο συγκεκριμένα, έστω ~w~ ένα δείγμα μήκους ~n~. Η λέξη ~w_{a,b}~ προκύπτει παίρνοντας όλους τους χαρακτήρες από τη θέση ~a~ στη θέση ~b~ στο δείγμα ~w~. Το βάρος του δείγματος ~w~ ορίζεται ως ο αριθμός των διαφορετικών ζευγών ακέραιων αριθμών ~a~, ~b (1 \le a \le b \le n)~ τέτοιοι ώστε η λέξη ~w_{a,b}~ να είναι παλίνδρομο.
Σας δίνεται το δείγμα ~w~. Μπορεί είτε να μείνει αμετάβλητο, είτε να επιλεγεί ακριβώς μία θέση και το γράμμα σε αυτή τη θέση να αλλάξει αυθαίρετα. Βρείτε το μέγιστο δυνατό βάρος δείγματος που μπορεί να είναι ληφθεί όπως περιγράφεται παραπάνω.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει το δεδομένο δείγμα ~w~ - μια σειρά από πεζά γράμματα του αγγλικού αλφαβήτου.

Έξοδος

Πρέπει να εκτυπώσετε το απαιτούμενο μέγιστο δυνατό βάρος.

Βαθμολογία

Έστω ~n~ το μήκος του δεδομένου δείγματος.

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	17	~1 \le n \le 100~
2	37	~101 \le n \le 5\,000~
3	46	~ 5001 \le n \le 100\,000~

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

input

aaaa

output

10

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

Κάθε υποσυμβολοσειρά είναι ήδη παλίνδρομο, οπότε καλύτερα να παραμείνει αμετάβλητο.

input

baccb

output

9

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

Αν αλλάξουμε το δεύτερο γράμμα του δείγματος σε "~c~", θα πάρουμε το δείγμα "~bcccb~" με βάρος ~9~.

input

slavko

output

7