题目描述

黑大帅 收到了一条非空的字符串。

一个非空字符串，如果从左到右和从右到左读取时都是相同的，被称为回文字符串。例如，字符串 abcba、a 和 abba 是回文字符串，而 abab 和 xy 则不是。

而同时，一个字符串被称为另一个字符串的子串，如果它可以通过从该字符串的开头和结尾删除一些（可能为零）字符来获得。例如，abc、ab 和空是字符串 abc 的子串，而 ac 和 d 则不是。

黑大帅 对于字符串的回文性质十分痴迷，因此，对于一个字符串，他定义了一个叫做回文度的概念：一个字符串的回文度是指字符串中有多少个非空子串是回文字符串。

现在，黑大帅 希望你对他收到的字符串重新调整字符顺序，使得新字符串的回文度最大。

输入描述

输入共一行，仅由小写英文字母组成，代表黑大帅收到的字符串。

输出描述

输出一个正整数，代表最后黑大帅 对收到的字符串重新调整字符顺序后可以达到的最大的回文度。

样例输入1

gagadbccghhchbdf

样例输出1

28

样例输入2

aqq

样例输出2

4

样例解释2

一种可能的重排后的字符串为 qaq，此时的回文度为 $4$。所有的回文子字符串为：q, a, q, qaq。

样例输入3

aaabb

样例输出3

9

样例解释3

一种可能的重排后的字符串为 ababa，其回文度为 $9$，所有为回文的子串如下：a, aba, ababa, b, bab, a, aba, b, a。

数据范围

本题共存在 $50$ 个测试点，各测试点详细信息见下表。