E. Binary Search Tree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

A binary tree is a tree data structure where each node has at most two children which are referred to as left child and right child. A binary search tree is a binary tree where each node has a comparable key and must satisfy the following conditions:

  • The left sub-tree of a node contains only nodes with keys less than the node’s key.
  • The right sub-tree of a node contains only nodes with keys more than the node’s key.
  • The left and the right sub-tree are also binary search tree.

Given a binary tree, your task is to choose a maximal set S of connected nodes in the given tree so that these nodes and the relations (left child, right child, or ancestor) among them form a binary search tree.

Input

The first line of input is the number T (T ≤ 20).

Then T tests follow:

  • The first line of each test is the number N (1 ≤ N ≤ 105) - the number of node of the given binary tree
  • Then N lines follow. The ith line describes node numbered i (nodes are numbered 1 to N). Each node is described by 3 integers: the index of its left child, the index of its right child, and the comparable key in that node. The value of a key will not exceed 106. If a node doesn’t have a left child and/or a right child, they will be represented as 0. The root node is numbered 1.
Output

For each test, print the maximal size of S.

Examples
Input
2
8
2 3 10
4 5 5
6 7 15
0 0 3
0 0 7
0 0 17
0 8 13
0 0 14
3
0 2 5
0 3 6
0 0 7
Output
5
3
Note

The example test case correspond to the following figure: