Score : $700$ points

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.

aabxyyzz

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.

byebye

1

byebye can be permuted to form a palindrome byeeyb.

abcdefghijklmnopqrstuvwxyz

26

abcabcxabcx

3

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