Zhang 教授听说，除非 $P = NP$，否则最长路径问题在任意图上都无法在多项式时间内解决。现在，Zhang 教授希望在某些特定的图上能在多项式时间内解决该问题。

最长路径问题是指在给定图中寻找一条长度最大的简单路径。如果一条路径没有重复的顶点，则称其为简单路径。路径的长度是指该路径中边的数量。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$（约 350），表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 10^4$, $n \le m \le n + 4$)，分别表示顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示顶点 $a_i$ 和 $b_i$ 之间的一条边 ($1 \le a_i, b_i \le n, a_i \neq b_i$)。

保证图是连通的且不包含重边。

输入总大小不超过 4 MB。

输出格式

对于每个测试用例，输出一个整数，表示最长路径的长度。

样例

输入 1

3
5 5
1 2
2 3
3 4
4 5
5 1
7 7
1 2
2 3
3 4
4 5
5 1
5 6
4 7
7 10
1 2
2 3
3 4
4 5
1 5
2 5
3 5
1 6
5 6
4 7

输出 1

4
6
6