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.

Examples

Input

aabxyyzz


Output

2


Input

byebye


Output

1


Input

abcdefghijklmnopqrstuvwxyz


Output

26


Input

abcabcxabcx


Output

3
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char c;
int now,f[67109000];
int main() {
	c=getchar();
	for (int i=1;i<67109000;i++)
	f[i]=1000000;
	f[0]=0; now=0;
	while (c>='a'&&c<='z') {
		int w=c-'a';
		now=now^(1<<w);
		//f[now]++;
		for (int i=0;i<26;i++)
		f[now]=min(f[now],f[now^(1<<i)]+1);
		//printf("%d %d\n",now,f[now]);
		c=getchar();
	}
	printf("%d\n",max(f[now],1));
	return 0;
}