THREECOL  Threecoloring of binary trees
A tree consists of a node and some (zero, one or two) subtrees connected to it. These subtrees are called children.
A specification of the tree is a sequence of digits. If the number of children in the tree is:
 zero, then the specification is a sequence with only one element '0';
 one, the specification begins with '1' followed by the specification of the child;
 two, the specification begins with '2' followed by the specification of the first child, and then by the specification of the second child.
Each of the vertices in the tree must be painted either red or green or blue.
However, we need to obey the following rules:
 the vertex and its child cannot have the same color,
 if a vertex has two children, then they must have different colors.
How many vertices may be painted green?
Task
Write a program which:
 reads the specification of the tree from the standard input,
 computes the maximal and the minimal number of vertices that may be painted green,
 writes the results in the standard output.
Input
The number of test cases t is in the first line of input, then t test cases follow in separate lines. Each test case consists of one word (no longer then 10000 characters), which is a specification of a tree.
Output
Your program should write for each test case exactly two integers separated by a single space, which respectively denote the maximal and the minimal number of vertices that may be painted green.
Example
Sample input: 1 1122002010 Sample output: 5 2
hide comments
mastik5h_1998:
20171218 16:45:32
easy one :) 

rahulpadhy:
20170104 06:51:43
There's no empty line between test cases..


ravi:
20160930 08:58:40
nice and easy 

praval_singhal:
20160913 10:20:51
Solved a DP question almost after a month, AC in 1 go.... :) 

itissabbir:
20160404 11:07:14
Its very easy DP for me .. AC in one go


Sumit Vohra:
20160215 14:40:59
DP on tree :)


ANVER S R:
20150207 15:49:10
the following are the output obtained while running the program in my laptop.


ANVER S R:
20150207 08:52:12
check why i am getting wrong answer?


mafo:
20090317 16:13:14
Beware !

Added by:  Piotr Ćowiec 
Date:  20040913 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  6th Polish Olympiad in Informatics, stage 3 