# 数叶子

### 样例1

#### 输入

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

#### 输出

7
7
3
3
3
63
63
63
51
31
31
31
31
31
31

### 数据范围

20% $1\le T\le 10,2\le n\le 15$

60% $1\le T\le 10,2\le n \le 2000$

100% $1\le T\le 1000, 2\le n\le 200000,2\le \sum n\le 200000$