Statement
在夏季，欧洲的古老城市里挤满了游客，他们在街道上漫步，参观各个兴趣点。
许多古老城市是有机地建造的，并非按照某种建筑规划，但奇怪的是，它们的扩张呈现出相似的模式：城市从三个兴趣点开始，每对兴趣点之间由一条双向街道连接；然后，逐渐添加新的兴趣点。任何新的兴趣点都通过两条新的双向街道连接到两个不同的、已经由一条街道直接相连的先前兴趣点。
一位参观这样城市的游客想要进行一次游览，访问尽可能多的兴趣点。游览可以从任意兴趣点开始，并且必须结束于同一个兴趣点。游览最多经过每条街道一次，每个兴趣点最多一次（除了第一个兴趣点恰好访问两次）。
给定城市如何扩张的描述。求一次游览在此城市中最多能访问的不同兴趣点的数量。
Input
输入文件的第一行包含案例数 T。接下来是 T 个测试案例。
每个案例以整数 N 开始——城市中兴趣点的总数。点用 1 到 N 的数字表示；数字 1、2、3 表示城市开始时的三个原始点，而数字 4、...、N 表示按添加到城市顺序的其他点。
接下来的 N-3 行每行包含一对空格分隔的整数 A、B，表示相应的兴趣点通过街道连接到点 A 和 B。这些行中的第一行对应点 4，第二行对应点 5，等等。
### 数据范围
- 1 ≤ T ≤ 50.
- 4 ≤ N ≤ 15.
- 4 ≤ N ≤ 1000.
Output
对于每个测试案例，按测试用例顺序逐个输出答案，输出一行包含 y，其中 y 是游览在此城市中最多能访问的兴趣点数量。
Examples
Input
2
5
1 2
2 1
6
1 2
1 4
4 5Output
4
6Constraints
- Time limit: 10000 ms
- Memory limit: 1048576 KB
- Tag: dynamic-programming
- Tag: graph