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 \(S\) 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ự.

Example

abcadd

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|S| \le 9\), \(S\) chỉ gồm các ký tự a và b.
• Subtask \(2\) (\(30\%\) số điểm): \(|S| \le 9\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.