小杨同学有一张包含 n 个结点的无向图 G，G 中的结点依次以 1, 2, \ldots, n 编号。

小杨同学发现 G 中每个结点的度数都是 2。显然 G 中恰好有 n 条边。

小杨同学想为 G 中的结点染色，使得任意一条边两端的结点都有不同的颜色。

小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为 G 染色。

本题包含多组数据。

第一行，一个正整数 t，表示数据组数。

对于每组数据：

• 第一行，一个正整数 n，表示无向图 G 中的结点数。
• 接下来 n 行，每行两个正整数 u_i、v_i，表示一条连接结点 u_i 与 v_i 的无向边，整数之间以空格分隔。

保证 G 中没有重边与自环。

对于每组数据：输出一行，一个整数，表示在满足条件的前提下为 G 染色需要的最少颜色数。

提示

数据范围

• 对于 40\% 的测试点，保证 \sum n \le 500（\sum n 指每个输入中多组数据的 n 的总和）。
• 对于 100\% 的测试点，保证 1 \le t \le 100，3 \le n \le 10^5，\sum n \le 10^5，保证 G 中没有重边与自环。