Một trò chơi xếp chữ trên điện thoại, người chơi có một chuỗi ký tự s. Mỗi lượt chơi được phép xóa một ký tự bẩt kỳ. Trò chơi kết thúc khi chuỗi còn lại là palindrome (đọc xuôi ngược như nhau).

Ví dụ: chuỗi "aca" hoặc "racecar" là chuỗi palindrome.

Yêu cầu: Tìm số lượt chơi ít nhất để chuỗi ban đầu trở thành palindrome.

Dữ liệu vào: WORDGAME.INP: chuỗi ký tự s (1 ≤ độ dài ≤ 2000, chỉ gồm chữ thường).

Dữ liệu ra: WORDGAME.OUT: số lượt chơi ít nhất.

Ví dụ minh họa chi tiết:

Input 01:

abcca

Output 01:

1

Input 02:

abacda

Output 02:

3

Input 03:

racecar

Output 03:

0

Input 04:

abcde

Output 04:

4

Input 05:

ababa

Output 05:

0

Input 06:

programming

Output 06:

7