题目描述

Tanaka 有一棵包含 $N$ 个节点的树，节点编号为 $1\sim N$。他希望把每个节点染成白色或黑色，使“兄弟节点对”的数量最大。

两个不同节点称为一对兄弟，当且仅当：

• 它们都被染成白色；并且
• 它们之间的简单路径满足以下条件之一：
  • 两点直接由一条边相连；
  • 路径上的中间节点全部为黑色。

换句话说，两白点之间如果直接相邻，或中间只隔着黑点，就会贡献一对。

任务

给定一棵树，求通过给节点染黑/白能够得到的最大兄弟节点对数量。

输入格式

第一行包含一个正整数 $T$，表示测试组数。

接下来给出 $T$ 组测试。每组测试：

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $x,y$，表示树中的一条边。

输出格式

包含 $T$ 行，第 $i$ 行输出第 $i$ 组测试的答案。

数据范围与限制

• $1\le T\le 10$
• $1\le N\le 5000$
• 每条边满足 $1\le x,y\le N$，且 $x\ne y$

子任务：

• 5 分：$T=1$ 且 $N\le 15$
• 10 分：$T=1$ 且 $N\le 20$
• 5 分：所有树恰有 2 个叶子，且 $N\le 500$
• 10 分：所有树中所有叶子只连到某条链两端的两个节点上，且 $N\le 500$
• 50 分：$N\le 500$
• 20 分：无额外限制

样例

输入

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

输出

7
1

样例解释

第一棵树中，最优染色可以得到 7 对兄弟节点。第二棵树只有两个相邻节点，把二者都染成白色即可得到 1 对。