大家都知道，在雅盖隆大学（Jagiellonian University），我们非常热爱植物。我们已经创作了数百道关于树、森林甚至仙人掌的题目！遗憾的是，关于动物的题目并不那么受欢迎。今天，我们想证明我们也同样热爱动物。

如果一个简单连通无向图的顶点数与边数相等，我们称其为“水母图”（jellyfish）。给定一个具有 $n$ 个顶点的水母图 $J$。对于任意顶点子集 $S \subseteq J$，如果对于每一个 $T \subseteq S$，都存在一个水母图的连通子图，该子图包含 $T$ 中的每一个顶点，且不包含 $S$ 中的任何其他顶点，则称 $S$ 为一个“极佳子集”（awesome subset）。

求 $J$ 的极佳子集的最大可能大小。

输入格式

输入的第一行包含测试用例的数量 $z$。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($3 \le n \le 100\,000$)，表示水母图的顶点数。

接下来的 $n$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i \neq v_i \le n$)，对应水母图的边。保证给定的图是一个水母图，且任意两个顶点之间最多只有一条边。

所有测试用例的顶点总数不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示该水母图极佳子集的最大可能大小。

样例

输入格式 1

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

输出格式 1

4
3