Maximum Sum Path in a Binary Tree

Your task is to determine the maximum possible sum of a simple path between any two nodes (possibly the same) in a given binary tree of 'N' nodes with integer values.

Explanation:

A simple path is defined as a path between any two nodes of a tree, such that no edge in the path is traversed more than once. The path's sum is the summation of all node values along the path.

Input:

The first line of input contains an integer 'T', representing the number of test cases. Subsequent lines for each test case provide the node values in level order form, separated by a space. Use -1 to signify a null node. The structure is flattened to a single line for each test case.

Output:

For each test case, output the maximum sum of a simple path between any two nodes in the tree. Provide each result on a new line.

Example:

Input:

1
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

18

Explanation:

The input represents a binary tree where the maximum sum simple path is 5 (from node 7, through nodes 4, 2, and 1, to node 3).

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 3000
• -105 ≤ data ≤ 105, data ≠ -1

Note:

The example input format explanation demonstrates how to flatten a tree's level order traversal into a single input line.