A binary tree can be represented as a sequence of characters consisting of 0, 1, and 2, which we call a "binary tree sequence $S$", according to the following rules:

$$ S = \begin{cases} 0 & \text{the node has no children} \\ 1S_1 & \text{the node has one child, where } S_1 \text{ is the sequence of the child} \\ 2S_1S_2 & \text{the node has two children, where } S_1 \text{ and } S_2 \text{ are the sequences of the two children} \end{cases} $$

For example, the binary tree shown in the figure below can be represented by the binary tree sequence $S=21200110$.

Your task is to color the nodes of a binary tree. Each node can be colored red, green, or blue. Furthermore, a node must have a different color from its children, and if a node has two children, those two children must also have different colors from each other. Given a binary tree sequence, find the maximum and minimum number of nodes that can be colored green.

Input

The input consists of a single line containing a binary tree sequence of no more than 10,000 characters.

Output

The output consists of a single line containing two integers, representing the maximum and minimum number of nodes that can be colored green, respectively.

Examples

Input 1

1122002010

Output 1

5 2