Given a general tree,
being *s* its size (its number of elements),
and being *h* its height.
The quotient *s*/*h* is a measure of how much “flattened” is the tree.

(To see some instances, consult the pdf or ps version of this wording.)

Write a program that reads the shape of various general trees,
and for each one
prints the maximal quotient *s*/*h* of all its subtrees.

**Input**

Input starts with *m*, the number of trees that must be treated
The description of the *m* trees follow
as is explained at the exercise : “”, with two exceptions:
The values are not given,
because the content of the nodes here is not important.
The number of nodes is neither given,
because you do not need to store the trees in any vector to solve this exercise.

**Output**

Your program must print with three figures the maximal quotient *s*/*h*
of the subtrees of each given tree.

Public test cases

**Input**

3 3 2 0 1 1 0 0 4 0 0 0 0 2 1 0 0 2 0 0

**Output**

2.500 1.333 1.500

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++