숌 언어

과학자들은 오래전에 찬란한 문명을 이루었던 숌이라는 나라에 관심을 가져 왔다. 마침내 2008년에 과학자들은 숌에서 쓰이던 언어인 숌어를 찾아냈다.

숌어에는 두 종류의 상형문자가 있다. 한 종류는 알파벳 대문자와 매우 비슷하고, 다른 한 종류는 알파벳 소문자와 매우 비슷하다. 편의상 이 두 종류를 각각 대문자와 소문자라고 부르자.

숌어 문장은 인접한 문자끼리 서로 다른 종류여야 한다. 즉 대문자와 소문자가 번갈아 나와야 한다. 예를 들어 AaAbBaAcCaAa는 올바른 문장이지만, ACbD는 올바른 문장이 아니다.

숌어의 단어는 항상 두 글자이며, 서로 다른 종류의 문자 한 쌍으로 이루어진다. 예를 들어 Aa, bB, bC는 올바른 단어이고, AA, aa, BE는 올바른 단어가 아니다.

숌 사람들은 단어를 겹쳐 써도 의미를 이해할 수 있다. 예를 들어 AaAbB라는 문장은 Aa, aA, bB라는 단어를 사용해 만들 수 있다.

이 규칙 때문에 같은 문장을 만들 수 있는 단어 집합은 여러 가지가 될 수 있다. 예를 들어 AaAbBaAcCaAa라는 문장은 Aa, aA, bB, cC라는 네 단어로 만들 수 있다.

어떤 숌어 문장이 주어졌을 때, 그 문장을 다시 만들기 위해 필요한 서로 다른 단어 수의 최솟값을 구하라.

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

첫째 줄에 주어진 문장을 만들기 위해 필요한 서로 다른 단어 수의 최솟값을 출력한다.