Mafuyu 躲藏在 Sekai 中，Kanade 正在寻找她。

在 Sekai 中，除了许多房间外别无他物。Sekai 中有 $n$ 个房间，编号从 $1$ 到 $n$。此外，有 $n - 1$ 对房间由走廊直接相连，使得可以通过一条或多条走廊从一个房间到达任何其他房间。换句话说，Sekai 中的房间构成了一棵树。

Kanade 位于房间 $1$，她知道 Mafuyu 可能以均匀的概率躲藏在除房间 $1$ 以外的任何房间中。在每一秒内，Kanade 可以移动到与她当前所在房间相邻的房间。一旦 Kanade 与 Mafuyu 处于同一个房间，她就会立即找到她。如果 Kanade 采取最优策略，她找到 Mafuyu 的最小期望时间是多少？

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 1\,000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 100$)，表示房间的数量。

接下来的 $n - 1$ 行，每行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，表示由第 $i$ 条走廊连接的房间。保证可以通过一条或多条走廊从一个房间到达任何其他房间。

输出格式

输出 $t$ 个实数。对于每个测试用例，输出最小期望时间。如果你的答案与标准答案的绝对误差或相对误差小于 $10^{-9}$，则被视为正确。

样例

输入 1

4
2
1 2
5
1 2
2 3
3 4
1 5
7
1 2
1 3
2 4
2 5
3 6
3 7
10
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10

输出 1

1.0000000000
3.2500000000
5.3333333333
8.0000000000