Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Input format
Line1: Number of Test cases (T)

Line2 to X: First Test Case’s binary tree structure (refer section below for the format)

LineX+1 to Y: Second Test Case’s binary tree structure and so on.

Output format
Print the maximum height of the tree.

Sample Input 1
1

6

1 2 3 4 5 6

1 2 3

2 4 -1

3 -1 5

4 -1 6

5 -1 -1

6 -1 -1

Sample Output 1
4

Explanation 1
Input Visualization:

image

In the given input the height of the tree is 4.

Constraints
1<=T<=100

1<=N<=100000

Sum of the number of nodes in all test cases will be less than 500000.

Instructions to create custom input for a Binary Tree
In order to specify a binary tree that can be used as custom input to the problem, you’ll need to follow this convention.

Line 1: Number of nodes in the Binary Tree (N)

Line 2: N space separated node values. The position of the Nodes on this line will be used to refer to them in the below lines, starting from 1.

Line 3 to N+2: Lines specifying the child nodes for each of the N nodes


Format of each line (space separated): Parent_node Left_child_node Right_child_node

Parent_node - Node at this Position on Line 2 is the Node to which we are assigning the Left and Right child here

Left_child_node - Node at this position on Line 2 is the left child. Specify -1 if there is no Left child.

Right_child_node - Node at this position on Line 2 is the right child. Specify -1 if there is no Right child.

Example1
image
/*
// Definition for TreeNode
class TreeNode {
public:
    long val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* next;
    TreeNode (long x) {
        val = x;
        left = NULL;
        right = NULL;
        next = NULL;
    }
*/
#include <bits/stdc++.h>
#include "../crio/cpp/io/FastIO.hpp"
#include "../crio/cpp/ds/TreeNode/TreeNode.hpp"

using namespace std;

class MaximumDepthOfBinaryTree {
public:
    int maxDepth(TreeNode* root) {
    }
};

int main() {
    FastIO();
    int t;
    cin >> t;
    while (t--) {
        TreeNode* root  = TreeNode().readTreeReturnRoot();
        int result = MaximumDepthOfBinaryTree().maxDepth(root);
        cout << result << endl;
    }

    return 0;
}