TOPALIN - Palindrome String

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Cho một xâu ký tự, bạn có thể biến đổi xâu này theo cách sau: Chọn một loại ký tự, biến đổi tất cả các ký tự loại này trong xâu thành một loại ký tự khác. Chi phí của một phép biến đổi như vậy bằng số lượng ký tự đã bị thay đổi. Bạn được phép áp dụng các phép biến đổi nhiều lần, chi phí của nhiều phép biến đổi bằng tổng chi phí của từng phép biến đổi.

Ví dụ, nếu bạn có xâu acaabc , sau khi biến tất cả các ký tự c thành b , bạn có xâu abaabb , bạn mất một lượng chi phí là 2 cho phép biến đổi này do có 2 ký tự c bị thay đổi.

Yêu cầu: Tìm chi phí nhỏ nhất để biến đổi một xâu trở thành xâu đối xứng .

Input

  • Một dòng duy nhất ghi xâu ban đầu.

Output

  • Một số duy nhất thể hiện chi phí tối ưu.

Example

Input:
acaabc

Output:
3

Giới hạn

  • Độ dài xâu không vượt quá 10 5 .
  • Mỗi ký tự trong xâu là chữ cái hoặc chữ số.
  • Trong 50% số test, độ dài xâu không vượt quá 100.

  • Người up: voj
  • Nguồn bài: VNOI Marathon 2009 - Warm up Round