1492 : 手中抓住了未来

zcy常擅长数据结构。一日，Enal正在学习二叉树。zcy假装自己是蒟蒻，问Enal一道数据结构题：
有一棵$n$个结点的二叉树$G$，现在新添加$k$个结点获得完全二叉树$G'$，求$k$的最小值。

输入分为多组测试数据，第一行输入$T$，表示有$T$组测试数据。
接下来，对于每一组测试数据，第一行输入$n$。接下来$n-1$行，每一行输入两个正整数$u_i,v_i$和一个取值仅可能为$0$或$1$的数$s_i$，当$s_i=0$时，表示结点$u_i$有一个左儿子$v_i$；当$s_i=1$时，表示结点$u_i$有一个右儿子$v_i$。
输入保证每组数据都能构成一棵二叉树。
$1 \leq T \leq 100$，$1 \leq u_i,v_i \leq n \leq 10000$，$s_i \in \{ 0,1 \}$。

对于每一组测试数据，在一行内输出答案。

3
5
1 2 0
1 3 1
2 4 0
2 5 1
4
1 2 0
1 3 1
3 4 1
6
3 1 0
3 2 1
2 6 1
2 4 0
1 5 0

0
3
1

下图为第一组测试数据表示的二叉树。

Enal