Problem Description

给定一棵 $n$ 个节点的树，节点的编号是 $1...n$，1 号点是它的根。

我们想通过一系列操作把它变成一棵二叉树。

对于每次操作，我们可以把一个叶子节点 $x$ 变成另一个节点 $y$ 的儿子，代价是本次操作前 $x$ 与 $y$ 之间的距离（从 $x$ 到 $y$ 的简单路径经过几条边）。

问总代价最小是多少？

Input

第一行一个正整数 $test(1 \le test \le 100)$ 表示数据组数。

对于每组数据，第一行一个正整数 $n(1 \le n \le 100)$ 表示节点个数。

接下来 $n-1$ 行，每行两个整数 $x, y(1 \le x, y \le n)$ 描述一条树边。

数据保证读入的是一棵树。

Output

对于每组数据，输出一行一个整数表示答案。

2
1
4
1 2
1 3
1 4

0
2