Calculate Binary Tree Depth

You are given multiple test cases. In each test case, a binary tree is described by its nodes. Each node is given by three integers: the node's value and the values of its left and right children. A value of -1 indicates that the corresponding child is absent.

Your task is to build the binary tree and compute its depth, defined as the maximum number of edges from the root to a leaf. Mathematically, if we denote the depth of a node as \(d\), then for any node with left subtree depth \(L\) and right subtree depth \(R\), the depth of the node is given by:

However, note that the answer should be reported as the number of edges on this longest path. That is, if the tree contains only a single node, its depth is 0.

The input contains several test cases. Make sure to process all test cases and output the answer for each on a separate line.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, the first line contains an integer \(N\) representing the number of nodes in the tree.
• The next \(N\) lines each contain three space-separated integers: value l r. Here, value is the node's identifier (or value), and l and r are the values of its left and right children respectively (or -1 if a child does not exist).

For example:

1
3
1 2 3
2 -1 -1
3 -1 -1

outputFormat

For each test case, output a single integer on a new line representing the depth (i.e. the number of edges on the longest path from the root to a leaf) of the binary tree.## sample

1
1
1 -1 -1

0