题目描述

我们有一个由小写英文字母组成的字符串 $s$。Snuke 将 $s$ 分成一些非空子串。记所得到的子串依次为 $s_1$, $s_2$, $...$, $s_N$（这里，满足 $s = s_1 + s_2 + ... + s_N$）。Snuke 希望满足以下条件：

• 对于每个 $i$（$1 \leq i \leq N$），都可以对 $s_i$ 中的字符进行排列，得到一个回文串。

找出满足条件时 $N$ 的最小可能值。

约束条件

• $1 \leq |s| \leq 2 \times 10^5$
• $s$ 由小写英文字母组成。

输入

输入从标准输入中按以下格式给出：

$s$

输出

当满足条件的分割存在时，请输出 $N$ 的最小可能值。

示例输入1

aabxyyzz

示例输出1

2

一种可行方案是将 $s$ 分成 aabxyyzz = aab + xyyzz。这里，aab 可以排列成回文串 aba，xyyzz 可以排列成回文串 zyxyz。

示例输入2

byebye

示例输出2

1

byebye 可以排列成回文串 byeeyb。

示例输入3

abcdefghijklmnopqrstuvwxyz

示例输出3

26

示例输入4

abcabcxabcx

示例输出4

3

一种可行方案是将 $s$ 分成 abcabcxabcx = a + b + cabcxabcx。