在夏季，欧洲的古城里挤满了在街道上漫步并参观名胜古迹的游客。

许多古城是自然形成的，并非按照某种建筑规划建造，但奇怪的是，它们的增长呈现出相似的模式：城市最初有三个名胜点，每两个点之间都由一条双向街道连接；随后，新的名胜点逐渐被添加进来。每一个新添加的名胜点都会通过两条新的双向街道，连接到两个之前已经存在且彼此直接相连的名胜点。

一位参观此类城市的游客希望进行一次游览，尽可能多地访问不同的名胜点。游览可以从任意一个名胜点开始，并且必须回到同一个名胜点结束。游览过程中，每条街道最多只能经过一次，每个名胜点最多只能访问一次（除了作为起点的名胜点会被访问恰好两次）。

给定城市增长的描述，请找出单次游览中能够访问到的不同名胜点的最大数量。

输入格式

输入文件的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例以整数 $N$ 开头，表示城市中名胜点的总数。名胜点用 $1$ 到 $N$ 的数字表示；数字 $1$、$2$ 和 $3$ 表示城市最初的三个名胜点，而数字 $4, \dots, N$ 表示其他名胜点，按它们被添加到城市中的顺序排列。

接下来的 $N-3$ 行，每行包含一对以空格分隔的整数 $A$ 和 $B$，表示对应的名胜点通过街道连接到了名胜点 $A$ 和 $B$。这些行中的第一行对应名胜点 $4$，第二行对应名胜点 $5$，以此类推。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是单次游览中能够访问到的不同名胜点的最大数量。

样例

输入格式 1

2
5
1 2
2 1
6
1 2
1 4
4 5

输出格式 1

Case #1: 4
Case #2: 6