Shom Language

Scientists have long been interested in an ancient country called Shom, which once had a brilliant civilization. In 2008, they finally discovered Shomese, the language used in Shom.

Shomese uses two kinds of hieroglyphs. One kind looks very much like uppercase English letters, and the other kind looks very much like lowercase English letters. For convenience, call them uppercase and lowercase letters.

In a valid Shomese sentence, adjacent characters must have different kinds. Uppercase and lowercase letters must alternate. For example, AaAbBaAcCaAa is a valid sentence, but ACbD is not.

A Shomese word always has length two and consists of one character of each kind. For example, Aa, bB, and bC are valid words, while AA, aa, and BE are not.

People of Shom can understand words even when they are written with overlaps. For example, the sentence AaAbB can be made using the words Aa, aA, and bB.

Because of this rule, there may be many possible sets of words that can make the same sentence. For example, the sentence AaAbBaAcCaAa can be made with the four words Aa, aA, bB, and cC.

Given a Shomese sentence, find the minimum number of distinct words needed to make that sentence again.

The first line contains a Shomese sentence. Its length is at most 2,500. The sentence consists only of English letters, and uppercase and lowercase letters always alternate.

Print the minimum number of distinct words needed to make the given sentence.