Maximum Root-to-Leaf Path Sum

You are given one or more binary trees. Each binary tree is represented by a list of nodes. Each node is described by three integers: val, left, and right, where val is the value of the node, and left and right are the 1-indexed positions of the left and right children respectively. If a child does not exist, its index will be -1.

Your task is to compute the maximum path sum from the root to any leaf for each binary tree. Formally, for each tree \( T \) with root \( r \), you need to find:

[ \text{maxPathSum}(T) = \max_{p \in \mathcal{P}(r)} \sum_{v \in p} v. ]

Here, \( \mathcal{P}(r) \) denotes the set of all root-to-leaf paths in \( T \). Every tree will have at least one node.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N_1
val_1 left_1 right_1
val_2 left_2 right_2
... (for N_1 nodes)
N_2
... (for next tree)
...

Here:

• T is the number of test cases (binary trees).
• For each test case, the first line is an integer N denoting the number of nodes in the tree.
• Then follow N lines, each containing three integers: the value of the node, and the indices of its left and right children (use -1 if a child does not exist). The nodes are given in order with indices from 1 to N.

outputFormat

For each test case, output the maximum root-to-leaf path sum on a new line to standard output (stdout).

## sample

1
1
3 -1 -1

3

</p>