题目描述

米浴是一名来自特雷森学院的赛马娘，她正在上数据结构课！

在数据结构课中，她学习了 AVL 树。AVL 树是一种基于树高的二叉搜索树，二叉树 $T$ 的树高是这么定义的：

• 如果 $T$ 是空的，那么 $h_T = 0$;
• 否则，假设 $T$ 的根为 $u$，$l_{su}$ 和 $r_{su}$ 分别表示 $u$ 的左子树和右子树（都有可能是空的）。此时，$h_T = \max(h_{ls_u}, h_{rs_u}) + 1$。

称一颗有根二叉树 $T$ 为AVL树，当且仅当：

• $T$ 是空的，或者
• 假设 $T$ 的根为 $u$，$u$ 的左子树和右子树（都有可能是空的）$l_{su}$ 和 $r_{su}$ 均为 AVL 树，且 $|h_{ls_u} - h_{rs_u}| \leq 1$。

现在，米浴有一颗根为 1 的二叉树，但是这棵树可能不是 AVL 树。为了把这棵树变成一颗 AVL 树，她可以进行任意多次如下的操作，每次操作在以下三种方式中选择一个：

• 删除一个叶子。
• 选择一个左子节点为空的节点，并创建一个新顶点作为它的左子节点。
• 选择一个右子节点为空的节点，并创建一个新顶点作为它的右子节点。

她想知道，最少几次操作可以让这棵树变成 AVL 树。

输入格式

本题有多组数据。第一行一个正整数 $T$ ($1 \leq T \leq 10000$) 表示数据组数。

对于每组数据，第一行一个整数 $n$ ($1 \leq n \leq 2 \times 10^5$)，表示当前的树的节点数。

接下来 $n$ 行，第 $i$ 行两个整数 $l_{si}, r_{si}$ ($0 \leq l_{si}, r_{si} \leq n$)，表示 $i$ 的左儿子和右儿子，如果左儿子或者右儿子不存在，那么用 0 表示。

保证给定的树是一颗以 1 为根的二叉树，保证 $\sum n \leq 2 \times 10^5$。

输出格式

对于每组数据，输出一行一个整数，表示最少几次操作可以让这棵树变成 AVL 树。

3
3
0 2
3 0
0 0
4
0 2
3 4
0 0
0 0
5
0 2
3 0
4 0
0 5
0 0

1
1
3