Cho xâu ~S~ gồm các chữ cái Latin thường từ a tới z. Ta được phép xáo trộn tùy ý vị trí các ký tự trong xâu ~S~, sau đó cắt xâu thành các đoạn con sao cho tất cả các đoạn con thu được đều là xâu đối xứng. Mục tiêu là thực hiện việc cắt sao cho số lượng đoạn con tạo thành là ít nhất có thể.

Input

Một dòng duy nhất chứa xâu ký tự ~S~ ~(1 \le |S| \le 10^6)~ chỉ gồm các chữ cái Latin in thường.

Output

Ghi ra một số nguyên duy nhất là số lượng đoạn con đối xứng ít nhất có thể chia được sau khi đã xáo trộn các ký tự.

Scoring

Sample Input 1

abcadd

Sample Output 1

2

Notes

Một cách sắp xếp và cắt thỏa mãn số xâu đối xứng cắt nhỏ nhất: cadbda.