#2739 재재새와 팰린드롬

3 s   128 MB  

Description

재재새는 팰린드롬에 대해서 배웠다.

 

팰린드롬은 앞으로 읽으나, 뒤로 읽으나 같은 것을 말한다.

 

wowoto9772는 팰린드롬이 아니다.

(왜냐하면, 거꾸로 읽으면 2779otowow 이므로)

 

재재새는 깔끔한 것을 좋아한다.

wowoto에서 숫자만 버리고 wowoto를 뒤집은 문자열 otowow를 붙여

결국, wowotootowow 로 팰린드롬을 만들었다.

 

이제부터, 최대 길이 30만의 문자열이 들어온다.

이 문자열에 일부를 변형하고, 삭제하고, 특정 문자를 추가 할 수 있다. 이때 드는 비용은 각각 1이다.

 

최소의 비용으로 wowotootowow를 만들어 주면 된다.

 

 

 

Input

길이 30만 이하의 문자열이 들어온다. (단, 빈 문자열은 입력으로 들어오지 않는다.)

입력은 여러개의 테스트 케이스로 이루어져있다.

Output

각 테스트 케이스마다, 들어가는 최소 비용을 한 줄에 하나씩 출력해준다.

Sample Input

Sample Output

wowoto9772otowow
4

Source

wowoto9772