Deepest Leaf Sum

Given a binary tree represented in level order, where each integer denotes a node's value and a value of (-1) indicates a null (missing) node, compute the sum of the values at the deepest level of the tree.

For example, consider the tree constructed from the input sequence:
1, 2, 3, 4, 5, -1, 6.
The deepest level contains the nodes with values 4, 5, and 6, and their sum is (15).

If the tree is empty or invalid (e.g. the first value is -1), the output should be 0.

This problem can be efficiently solved by performing a breadth-first search (BFS) traversal, where the sum computed at the last level is the desired answer.

inputFormat

The input is read from standard input.

The first line contains an integer (T) denoting the number of test cases. Each test case is described as follows:
- The first line contains an integer (N), the number of nodes in the level order representation of the tree.
- The next line contains (N) space-separated integers representing the node values, where (-1) indicates a null node.

Note: For a test case with (N = 0), the tree is considered empty.

outputFormat

For each test case, output a single line containing one integer — the sum of the node values at the deepest level of the corresponding binary tree. The output is printed to standard output.## sample

5
7
1 2 3 4 5 -1 6
5
10 20 30 -1 40
0
7
1 2 3 -1 -1 4 5
1
7

15
40
0
9
7