Bessie は、$1\ldots N$ と番号付けされた $N$ 個の頂点と $M$ 本の辺を持つ連結な無向グラフ $G$ を持っています（$2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$）。$G$ は自己ループ（頂点から同じ頂点に戻る辺）を含むことがありますが、多重辺（同じ両端の頂点を結ぶ複数の辺）は含みません。

各 $1\le a\le N$ と $0\le b$ に対して、頂点 $1$ から頂点 $a$ へちょうど $b$ 本の辺を通る経路が存在するとき真、そうでないとき偽となる真偽値関数を $f_G(a,b)$ とします。同じ辺を複数回通る場合は、その回数だけ辺の数に数えます。

Elsie は Bessie のまねをしたいと思っています。具体的には、すべての $a$ と $b$ に対して $f_{G'}(a,b)=f_G(a,b)$ となる無向グラフ $G'$ を作りたいと考えています。

Elsie は作業量をできるだけ少なくしたいので、できるだけ小さいグラフを作りたいと思っています。したがって、あなたの仕事は $G'$ の辺の本数として可能な最小値を求めることです。

各入力には、独立に解くべき $T$ 個（$1\le T\le 5\cdot 10^4$）のテストケースが含まれます。すべてのテストケースにわたる $N$ の総和は $10^5$ 以下、$M$ の総和は $2\cdot 10^5$ 以下であることが保証されます。

入力

入力の最初の行には、テストケースの数 $T$ が含まれます。

各テストケースの最初の行には、2 つの整数 $N$ と $M$ が含まれます。

各テストケースの続く $M$ 行にはそれぞれ 2 つの整数 $x$ と $y$（$1\le x\le y\le N$）が含まれ、$G$ において $x$ と $y$ の間に辺が存在することを表します。

読みやすくするため、隣り合うテストケースは空行で区切られています。

出力

各テストケースについて、$G'$ の辺の本数として可能な最小値をそれぞれ別の行に出力してください。

入出力例

入力 1

2

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

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

出力 1

4
5

注記

最初のテストケースでは、Elsie は $G$ から $(2,5)$ を取り除くことで $G'$ を作れます。また、$G$ から辺を取り除くだけに制限されているわけではないので、次の辺を持つグラフを作ることもできます：

1 2
1 4
4 3
4 5

$G'$ も連結でなければならないので、Elsie が辺の本数を $N-1$ より少なくすることは絶対にできません。

入力 2

7

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

10 11
1 2
1 5
1 6
2 3
3 4
4 5
4 10
6 7
7 8
8 9
9 9

13 15
1 2
1 5
1 6
2 3
3 4
4 5
6 7
7 8
7 11
8 9
9 10
10 11
11 12
11 13
12 13

16 18
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
8 9
9 10
9 15
9 16
10 11
11 12
12 13
13 14
14 15
14 16

21 22
1 2
1 9
1 12
2 3
3 4
4 5
5 6
6 7
7 8
7 11
8 9
8 10
12 13
13 14
13 21
14 15
15 16
16 17
17 18
18 19
19 20
20 21

20 26
1 2
1 5
1 6
2 3
3 4
4 5
4 7
6 8
8 9
8 11
8 12
8 13
8 14
8 15
8 16
8 17
9 10
10 18
11 18
12 19
13 20
14 20
15 20
16 20
17 20
19 20

24 31
1 2
1 7
1 8
2 3
3 4
4 5
5 6
6 7
6 9
8 10
10 11
10 16
10 17
10 18
10 19
10 20
11 12
12 13
13 14
14 15
15 16
15 17
15 18
15 19
15 20
15 21
15 22
15 23
15 24
21 22
23 24

出力 2

10
11
15
18
22
26
31

注記

これらの各テストケースでは、Elsie は Bessie より辺の本数を少なくすることができません。

問題作成者：Benjamin Qi