Following the murder of King Osiris by his brother Set, the rightful heir Ra engaged his uncle in a struggle for the throne of Egypt. During the battle, Set tore out the right eye of Horus (a.k.a the Eye of Ra) and broke it into fragments.

Conviniently, the eye has broken into exactly two types of fragments: Pupil of Fire (6): Contains the heat of the sun but too unstable on it's own. Protective Brow (7): The only vessel capable of containing the Pupil's heat.

As a divine healer, Thoth was tasked with restoring the eye. This restored eye, the Eye of Ra, would allow Ra to become the rightful ruler of Egypt, but only if the fragments were combined in a precise order. A restoration is only successful if a Pupil is recovered before a Brow is found. Once a fragment is used in a pairing, it is consumed and cannot be reused.

Unfortunately, the fragments have been scattered across the shifting sands of the Duat. Thoth enlists the help of Maged and tasks him with collecting all the eye fragments determining the maximum number of complete Wedjat eyes that can be restored from a given sequence of fragments.

Input

The first line contains a single string ~s~ of length ~n~ ~(1 \leq n \leq 10^6)~ consisting of the digits 6 and 7, representing Pupils of Fire and Protective Brow's respectively.

Output

Output the maximum number of Eyes of Ra that can be restored.

Examples

Input 1

67

Output 1

1

• haha 67 🤣🤣🤣

Input 2

6677

Output 2

2

Input 3

776676

Output 3

1