Maximum Root-to-Leaf Path Sum

Given a binary tree, your task is to compute the maximum sum along any path from the root to a leaf node. For each node, the contribution is its integer value. Formally, if a path is defined as \(P = [node_0, node_1, \dots, node_k]\), then the sum is given by \(S = \sum_{i=0}^{k} node_i\). The tree is described by a list of nodes, where each node is represented by four integers: node_id, left_child_id, right_child_id, and node_value. A child id of \(-1\) denotes the absence of that child. It is guaranteed that the node with node_id = 0 is the root if it exists.

inputFormat

The input is read from stdin and is organized as follows:

• The first line contains an integer \(T\), the number of test cases.
• For each test case, the first line contains an integer \(n\), the number of nodes in the tree.
• This is followed by \(n\) lines, each containing four space-separated integers representing node_id, left_child_id, right_child_id, and node_value.

Note: A child id of \(-1\) indicates that the child does not exist.

outputFormat

For each test case, output a single line on stdout containing the maximum root-to-leaf path sum.

## sample

1
1
0 -1 -1 1

1

</p>