Description

现有一个使用孩子兄弟表示的树，请输出树的深度。

Input

输入的第一行是一个int型整数T，表示一个有T组数据。
每组数据先输入一个整数n（表示树有n个节点），
接下来2到n+1行，每行输入三个整数id，son和bro，表示id节点的第一个孩子是son，右兄弟是bro。如果son或bro为-1，则表示没有孩子或右兄弟。保证根节点的id为1。

Output

输出T行，每行一个整数，表示对应树的深度。

Sample Input

1
7
1 2 -1
2 5 3
3 6 4
4 -1 -1
5 -1 7
6 -1 -1
7 -1 -1

Sample Output

3