목걸이 제작

Yalda는 Bahar의 생일을 맞아 멋진 선물을 주려고 한다. Yalda는 서로 다른 색의 구슬 n개로 이루어진 목걸이의 스케치를 종이에 그려 두었다. 목걸이는 구슬의 색을 나타내는 알파벳 소문자로 이루어진 길이 n의 문자열로 표현된다. 알파벳 26자는 각각 서로 다른 색 하나씩을 나타낸다. Yalda는 자신이 가진 여러 색의 구슬을 무한히 많이 사용해 목걸이를 만들 것이다. 하지만 Bahar의 생일이 다가오는 탓에 시간이 얼마 없어서, 가능한 한 적은 단계로 목걸이를 만들고 싶어 한다. Yalda에게는 처음에 빈 목걸이 두 개가 있다. 하나는 최종 선물이 될 목걸이이고, 다른 하나는 제작 과정에서 Yalda를 돕는 임시 목걸이다. 각 단계에서 Yalda는 다음 중 하나를 할 수 있다.

• 임시 목걸이의 임의의 위치에 원하는 색의 구슬을 추가한다.
• 임시 목걸이의 임의의 위치에서 구슬 하나를 제거한다.
• 임시 목걸이의 구슬 하나를 원하는 색의 구슬로 교체한다.
• 임시 목걸이를 복사해 그 구슬열을 주 목걸이의 끝에 이어 붙인다. 이어 붙는 구슬열은 임시 목걸이와 정확히 같다. 다만 복사하는 동안 임시 목걸이의 구슬 순서는 뒤집힌다. 예를 들어 이 작업 전에 주 목걸이가 pq이고 임시 목걸이가 abc라면, 작업 후 주 목걸이는 pqabc가 되고 임시 목걸이는 cba가 된다.

Yalda는 목걸이를 만드는 데 필요한 최소 단계 수를 알려 주면 매우 고마워할 것이다.

입력은 한 줄이며, 알파벳 소문자로 이루어진 길이 300 이하의 비어 있지 않은 문자열이다. 이 문자열은 만들고자 하는 목걸이의 스케치를 나타낸다.

한 줄에 목걸이를 만드는 데 필요한 최소 단계 수를 나타내는 정수 하나를 출력한다.