Write a program that reads non empty binary trees of positive integer numbers, and for each one prints the greatest average of the elements of each subtree.

Input

Input starts with m, the number of trees that must be treated. The description of the m trees follows as it is explained at the exercise , with an exception: The number of nodes is not given, because you do not need to store the trees in any vector to solve this exercise. You can suppose that any of the given trees is empty.

Output

For each tree, your program must print with four decimals the greatest average of the elements of all its subtrees.

Public test cases

**Input**

2 3 0 7 -1 4.5 -1 -1 2 -1 -1 5 4 -1 -1 7.5 6 -1 1.5 -1 -1 -1 80 -1 50 -1 20 -1 -1

**Output**

5.7500 50.0000

Information

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