Given a binary tree represented by a sequence $S$, which consists of only characters 0, 1, and 2. The sequence $S$ is the preorder traversal sequence of the binary tree, where:

• 0 represents a node with 0 child.
• 1 represents a node with 1 child.
• 2 represents a node with 2 children.

For example, the binary tree in the following picture is represented by $S=2210010$.

Given the binary tree, you need to color this binary tree with three different colors: red, green, and blue. The requirements are:

• Every node must have a different color from its children.
• If a node has two children, the two children must have different colors.

Given the binary tree sequence $S$, find the maximum possible number of nodes and the minimum possible number of nodes colored in red.

Input Specification

The first line of input contains one string $S$ ($1\le |S|\le 5\times {10}^5$), indicating the sequence of the binary tree.

Output Specification

Output two integers in one line, the maximum possible number of nodes and the minimum possible number of nodes colored in red.

Constraints

Subtask	Points	Additional constraints
$1$	$50$	$|S|\le 2000$
$2$	$50$	No additional constraints

Sample Input 1

2210010

Sample Output 1

4 1

Explanation

The binary tree is shown in the above picture. To get the maximum possible number of nodes colored in red, we can color nodes $1$, $5$, $6$, $7$ in red. To get the minimum possible number of nodes colored in red, we can color the node $2$ in red.

Sample Input 2

1122002010

Sample Output 2

5 2