Maximum Valid String Partitioning

You are given a string s consisting only of lowercase letters.

A sequence of strings \(t_1, t_2, \ldots, t_k\) is considered valid if and only if:

• \(s = t_1+t_2+\cdots+t_k\) (the + here denotes string concatenation), and
• for all \(1 \le i \le k-1\), \(t_i \neq t_{i+1}\).

Your task is to find the maximum possible value of \(k\) for which there exists a valid partition of \(s\) into \(k\) segments.

Note: Even if two segments consist of the same character, they are considered equal if their string representations are exactly the same (e.g. "a" and "a" are equal). However, segments of different lengths (e.g. "a" and "aa") are considered different.

Hint: The problem can be solved by independently maximizing the number of segments within each maximal contiguous block of identical characters. For a block of length \(L\), you need to split it into parts such that no two adjacent parts are equal. It turns out that the maximum number of segments you can achieve in such a block is \(\left\lfloor\frac{2L+1}{3}\right\rfloor\).

inputFormat

The input consists of a single line containing the string s (\(1 \le |s| \le 10^5\)), which is composed only of lowercase letters.

outputFormat

Output a single integer representing the maximum possible number of segments, \(k\), for a valid partition of s.

sample

aaa

2