시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 645 177 139 37.772%

문제

팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.

만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다.

예를 들어 abaccbcb라는 문자는 aba, cc, bcb와 같이 세 개의 문자열로 나누면 각각 팰린드롬이 된다. 하지만 두 개의 문자열로 나누어서는 결코 각각이 모두 팰린드롬이 될 수 없다. 따라서 이 경우의 답은 3이다. 마찬가지로 anavolimilana와 같은 문자열은 ana, v, o, limil, ana의 다섯 개의 문자열로 나누면 각각 팰린드롬으로 만들 수 있으며, 네 개로 나누어서는 각각이 모두 팰린드롬이 되도록 만들 수 없다. 따라서 이 경우의 답은 5이다.

문자열이 주어졌을 때, 이 문자열을 최소 개수의 팰린드롬으로 나누는 프로그램을 작성하시오. 문자열 자체가 팰린드롬이라면 굳이 나눌 필요는 없다.

입력

첫째 줄에 단어가 입력으로 들어온다. 단어는 영어 소문자로만 이루어져 있으며, 그 길이는 2,000을 넘지 않는다.

출력

주어진 문자열을 최소 개수의 팰린드롬으로 나누었을 때, 그 개수를 출력한다.

예제 입력 1

anavolimilana

예제 출력 1

5
W3sicHJvYmxlbV9pZCI6IjIwNzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2YyhwYWxpbmRyb21lKVx1Yzc3NFx1Yjc4MCBcdWM1NWVcdWM1ZDBcdWMxMWNcdWJkODBcdWQxMzAgXHVjNzdkXHVjNzNjXHViMDk4IFx1YjRhNFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWM3N2RcdWM3M2NcdWIwOTggXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuICdhYmEnXHViMDk4ICdhJ1x1YzY0MCBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHViMjk0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YmE3MCwgJ2FiYWNjYmNiJ1x1YjA5OCAnYW5hdm9saW1pbGFuYSdcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzViNFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcbjxwPlx1YjljY1x1Yzc3YyBcdWM1YjRcdWI1YTQgXHViMmU4XHVjNWI0XHVhYzAwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM1NDRcdWIyYzhcdWI3N2NcdWJhNzQsIFx1YWRmOCBcdWIyZThcdWM1YjRcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWM3NzRcdWI5N2MgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViNDE4LCBcdWIwOThcdWIyMDRcdWM1YjRcdWM5YzQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YjA5OFx1YjIwNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBhYmFjY2JjYlx1Yjc3Y1x1YjI5NCBcdWJiMzhcdWM3OTBcdWIyOTQgYWJhLCBjYywgYmNiXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWIwOThcdWIyMDRcdWJhNzQgXHVhYzAxXHVhYzAxIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWMxMWNcdWIyOTQgXHVhY2IwXHVjZjU0IFx1YWMwMVx1YWMwMVx1Yzc3NCBcdWJhYThcdWI0NTAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzc0IFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWIyZjVcdWM3NDAgM1x1Yzc3NFx1YjJlNC4gXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHViODVjIGFuYXZvbGltaWxhbmFcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBhbmEsIHYsIG8sIGxpbWlsLCBhbmFcdWM3NTggXHViMmU0XHVjMTJmIFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViMDk4XHViMjA0XHViYTc0IFx1YWMwMVx1YWMwMSBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjEyNCBcdWFjMWNcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc3NCBcdWJhYThcdWI0NTAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1Yzc3NCBcdWFjYmRcdWM2YjBcdWM3NTggXHViMmY1XHVjNzQwIDVcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM3OTBcdWNjYjRcdWFjMDAgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHViNzdjXHViYTc0IFx1YWQ3M1x1Yzc3NCBcdWIwOThcdWIyMGMgXHVkNTQ0XHVjNjk0XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gXHViMmU4XHVjNWI0XHViMjk0IFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhZGY4IFx1YWUzOFx1Yzc3NFx1YjI5NCAyLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjOGZjXHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHVjNzU4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIwNzkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQQUxJTiIsImRlc2NyaXB0aW9uIjoiPHA+QSBwYWxpbmRyb21lIGlzIGEgd29yZCB0aGF0IGlzIHJlYWQgdGhlIHNhbWUgZm9yd2FyZCBvciBiYWNrd2FyZHMuIElmIGEgd29yZCBpcyBub3QgYSBwYWxpbmRyb21lLCBpdCBjYW4gYmUgY3V0IGludG8gcGFydHMgdGhhdCBhcmUgcGFsaW5kcm9tZXMuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgcGFsaW5kcm9tZSBwYXJ0cyB0byB3aGljaCBhIGdpdmVuIHNlcXVlbmNlIG9mIGNoYXJhY3RlcnMgY2FuIGJlIGN1dC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGZpbGUgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzLiBUaGUgY2hhcmFjdGVycyB1c2VkIGFzIGlucHV0IHdpbGwgYmUgZnJvbSB0aGUgc2V0IG9mIHNtYWxsIGxldHRlcnMgb2YgRW5nbGlzaCBhbHBoYWJldCAoYSZuZGFzaDt6KS4gVGhlIGxlbmd0aCBvZiBldmVyeSBpbnB1dCBzZXF1ZW5jZSB3aWxsIGJlIGF0IG1vc3QgMjAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgZmlsZSBzaG91bGQgY29udGFpbiByZXF1aXJlZCBudW1iZXIgb2YgcGFsaW5kcm9tZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d