시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB298685432.335%

문제

과학자들은 기원전 찬란한 문명의 꽃을 이루었던 숌이라는 나라에 대한 관심을 가지고 있다. 과학자들은 마침내 2008년 숌이라는 나라의 언어인 숌어를 찾아내었다.

숌어는 두 종류의 상형문자를 쓰는데, 하나는 알파벳 대문자와 정말 비슷하게 생겼고, 또다른 하나는 알파벳 소문자와 정말 비슷하게 생겼다. 따라서 그냥 알파벳 대문자와 소문자라고 말하기로 했다.

숌어로 문장을 쓸 때는, 인접한 단어끼리는 서로 다른 타입이어야 한다. 각기 다른 타입이 서로 번갈아가면서 나와야 한다. 예를 들면, AaAbBaAcCaAa는 맞는 문장이지만, ACbD는 틀린 문장이다.

과학자들은 숌어에도 단어가 있다는 사실을 깨달았다. 단어는 항상 두글자이고, 서로 다른 타입의 쌍으로 나타낸다는 것을 알았다. 예를 들면, Aa, bB, bC는 올바른 단어이지만, AA, aa, BE와 같은 것은 올바르지 않은 단어이다.

더욱 놀라운 사실은, 숌이란 나라에 사는 사람은 아이큐가 최소 430이기 때문에, 단어를 겹쳐서 써도 다 알아듣는다는 것이다. 따라서, AaAbB는 Aa aA bB를 이용해서 만들 수 있는 문장이다.

위와 같은 사실 때문에, 어떤 문장을 만들 수 있는 경우의 수가 많다는 사실을 알았다.

AaAbBaAcCaAa라는 문장이 있을 때, 이 문장은 Aa, aA, bB, cC 라는 4개의 단어를 가지고 만든 문장이다.

어떤 문장이 있을 때, 최소 몇 개의 단어를 이용해야 다시 이 문장을 만들 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문장이 주어진다. 문장의 길이는 최대 2,500이다. 문장은 알파벳으로만 이루어져있고, 항상 대문자와 소문자가 번갈아가면서 나온다.

출력

첫째 줄에 필요한 단어의 최솟값을 출력한다.

예제 입력 1

AaAbBaAcCaAa

예제 출력 1

4

예제 입력 2

AbAb

예제 출력 2

1

예제 입력 3

aBaB

예제 출력 3

1

예제 입력 4

AaBb

예제 출력 4

2

출처