Problem Description

You are given a string $ s $ consisting of lowercase English letters. Snuke is trying to split $ s $ into several non-empty substrings. Let the substrings after the split be $ s_1 $, $ s_2 $, $ ... $, $ s_N $ (thus, $s\ =\ s_1\ +\ s_2\ +\ ...\ +\ s_N$). Snuke wants to split $ s $ such that the following condition holds:

• For each $ i $ ($1\ \leq\ i\ \leq\ N$), $ s_i $ can be rearranged to form a palindrome.

Find the minimum value of $ N $ when $ s $ is split to satisfy the condition.

Input Format

The input is given from the standard input in the following format:

$ s $

Output Format

Output the minimum value of $ N $ when $ s $ is split to satisfy the condition.

Sample Input and Output

Sample Input #1

aabxyyzz

Sample Output #1

2

Sample Input #2

byebye

Sample Output #2

1

Sample Input #3

abcdefghijklmnopqrstuvwxyz

Sample Output #3

26

Sample Input #4

abcabcxabcx

Sample Output #4

3

Notes/Hints

Constraints

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

Sample Explanation 1

aabxyyzz can be split into aab + xyyzz. Here, aab can be rearranged to form the palindrome aba, and xyyzz can be rearranged to form the palindrome zyxyz.

Sample Explanation 2

The string byebye can be rearranged to form the palindrome byeeyb.

Sample Explanation 4

abcabcxabcx can be split into a + b + cabcxabcx.

见题面 Input 部分

见题面 Output 部分