题目描述

烤乐滋有一个仅含有小写字母的字符串 $s$，求出这个字符串需要至少添加多少个字符，才能将这个字符串拆分成两个完全相同的回文串，注意，加入字符后可以任意重排字符串。

输入格式

输入一个仅含有小写字母的字符串 $s$。

输出格式

输出最小的操作次数。

样例 #1

样例输入 #1

cfc

样例输出 #1

3

提示

【样例解释】

加上字符 $fff$，重排后可以使得回文串为 $fcf$。

【数据范围】

设 $|s|$ 为字符串 $s$ 的长度。

• Subtask1（97 pts）：保证 $1 \le |s| \le 10$。

• Subtask2（1 pts）：保证 $1 \le |s| \le 10^2$。

• Subtask3（1 pts）：保证 $1 \le |s| \le 10^4$。

• Subtask4（1 pts）：保证 $1 \le |s| \le 10^6$。