Count Diagonal Paths

You are given a binary tree. Your task is to return the count of the diagonal paths to the leaf of the given binary tree such that all the values of the nodes on the diagonal are equal.

Input:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The following ‘T’ lines represent the ‘T’ test cases.
Each test case line contains the elements of the tree in level order form, separated by a single space. Use -1 to denote a missing child.

Output:

For each test case, return the count of the diagonal paths to the leaf of the given binary tree such that all the values of the nodes on the diagonal are equal.

Example:

Input:
 5 6 5 -1 6 -1 5 -1

Output:
 2

Explanation:
 Diagonal 6 – 6 and 5 – 5 contains equal values. Therefore, the required output is 2.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• 1 <= data <= 10^9

Note:

The sequence in the input for the tree nodes is given in a single line with values separated by a single space, where -1 denotes a null node.
For example, for the tree: 

        1
       /    \
     4        2
    /  \        \
   8    5         3
       /  \       /
      9    7      6

The input will be: 1 4 2 8 5 -1 3 -1 -1 9 7 6 -1 -1 -1 -1 -1 -1