Description

对一棵树进行着色，每个结点可着黑色或白色，相邻结点不能着相同黑色，但可着相同白色。请设计一种算法对树中尽量多的节点着黑色。

Input

第一行输入T(T<=10)表示有T组数据。每组数据先输入一个正整数N(1<=N<=50000)，表示共有N个结点，接下来输入N-1对(u,v)，表示u与v之间有一条边。

Output

输出T行正整数，第i行表示第i棵树最多能着色几个黑点。

Sample Input

3
2
1 2
4
1 2
2 3
3 4
4
1 2
1 3
1 4

Sample Output

1
2
3