火凤燎原
题号：NC230907
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

从风暴中归来，在烈火中重生。

「蒲公英」是树上的一个连通子集，有且仅有一个「中心点」，另外：

设「中心点」在原树中的度为 ，则必须有 k-1 个结点在「蒲公英」中是一个单点，剩下一条链；那条链的本身长度（不包含 u）必须不少于 2。（下图中 0 号结点即为「中心点」而它的度为 6）



两个「蒲公英」本质不同，当且仅当中心点 u 不同或对应的链包含的结点不同。（至少存在一个结点 v 属于一个「蒲公英」而不属于另一个「蒲公英」）

给定一棵无根树，求其中「蒲公英」的个数。

输入描述:

全文第一行输入数据组数 。

对每组数据，第一行输入一个正整数 ，表示树的结点个数。

第  行输入两个正整数 ，表示一条树边。

输出描述:

输出本质不同「蒲公英」的个数。
示例1

输入

复制 
5
5
1 2
2 3
1 4
1 5
7
1 3
2 3
3 4
3 6
4 5
6 7
9
1 2
1 4
1 5
2 3
2 6
2 7
2 8
2 9
10
1 2
2 3
3 4
4 5
3 6
6 7
3 8
8 9
9 10
20
20 18
1 3
19 12
19 4
16 1
4 1
1 7
16 10
7 20
13 8
10 2
18 13
13 17
14 18
11 19
16 5
2 6
16 9
17 15

输出

复制 
1
2
7
5
78

说明

对于样例 #1，整棵树本身就是一个蒲公英。

对于样例 #2 \sim #4，样例解释如下图所示：