Problem Statement

We have a string $s$ consisting of lowercase English letters. Snuke is partitioning $s$ into some number of non-empty substrings. Let the subtrings obtained be $s_1$, $s_2$, $...$, $s_N$ from left to right. (Here, $s = s_1 + s_2 + ... + s_N$ holds.) Snuke wants to satisfy the following condition:

• For each $i$ ($1 \\leq i \\leq N$), it is possible to permute the characters in $s_i$ and obtain a palindrome.

Find the minimum possible value of $N$ when the partition satisfies the condition.

Constraints

• $1 \\leq |s| \\leq 2 \\times 10^5$
• $s$ consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$s$

Output

Print the minimum possible value of $N$ when the partition satisfies the condition.

Sample Input 1

aabxyyzz

Sample Output 1

2

The solution is to partition $s$ as aabxyyzz = aab + xyyzz. Here, aab can be permuted to form a palindrome aba, and xyyzz can be permuted to form a palindrome zyxyz.

Sample Input 2

byebye

Sample Output 2

1

byebye can be permuted to form a palindrome byeeyb.

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

26

Sample Input 4

abcabcxabcx

Sample Output 4

3

The solution is to partition $s$ as abcabcxabcx = a + b + cabcxabcx.