Cho một chuỗi str gồm các kí tự từ a->z. Ta có thể chọn 1 cặp kí tự ở gần nhau, giống nhau và xóa chúng. Hỏi sau khi thực hiện 1 loạt các thao tác trên thì chuỗi lúc này có độ dài nhỏ nhất là bao nhiêu.

Input: Nhập vào xâu S có độ dài không quá 10⁵.

Output: In ra số nguyên duy nhất là độ dài nhỏ nhất của chuỗi sao khi giảm.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

aaabbaac

Output

2

Giải thích ví dụ

• ~aaabbaac->abbaac->aaac->ac~.