D - Yet Another Palindrome Partitioning /

### 問題文

• i (1 \leq i \leq N) について、s_i の文字を並べ替えて回文が得られる。

### 制約

• 1 \leq |s| \leq 2 \times 10^5
• s は英小文字のみからなる。

### 入力

s


### 入力例 1

aabxyyzz


### 出力例 1

2


aabxyyzz = aab + xyyzz と分割すればよいです。 このとき、aab の文字を並べ替えて回文 aba が得られ、xyyzz の文字を並べ替えて回文 zyxyz が得られます。

### 入力例 2

byebye


### 出力例 2

1


byebye の文字を並べ替えて回文 byeeyb が得られます。

### 入力例 3

abcdefghijklmnopqrstuvwxyz


### 出力例 3

26


### 入力例 4

abcabcxabcx


### 出力例 4

3


abcabcxabcx = a + b + cabcxabcx と分割すればよいです。

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.

### 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.