暂无测试数据。

题目描述

蒜头君收到了一条 非空的字符串 。

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

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

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

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

输入描述

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

输出描述

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

数据范围

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

测试点编号	字符串长度 $n$	字符串满足的性质
$1\sim 5$	$1\leq n\leq 10$	任意随机字符串
$6\sim 10$	$11\leq n\leq 10^3$	任意随机字符串
$11\sim 15$	$10^3\leq n\leq 10^5$	任意随机字符串
$16\sim 20$	$1\leq n\leq 10$	字符串内所有的字符均相同
$21\sim 25$	$11 \leq n\leq 10^3$	字符串内所有的字符均相同
$26\sim 30$	$10^3 \leq n\leq 10^5$	字符串内所有的字符均相同
$31\sim 35$	$1\leq n\leq 10$	字符串由两种字符组成，其中一种字符只有一个
$36\sim 40$	$11\leq n\leq 10^3$	字符串由两种字符组成，其中一种字符只有一个
$41\sim 45$	$10^3\leq n\leq 10^5$	字符串由两种字符组成，其中一种字符只有一个
$46\sim 48$	$10^5\leq n\leq 5\cdot 10^5$	字符串内所有的字符均相同
$49\sim 50$	$10^5\leq n\leq 5\cdot 10^5$	任意随机字符串

gagadbcgghhchbdf

29

aqq

4

aaabb

9