Bessie ma spójny, nieskierowany graf $G$ z $N$ wierzchołkami oznaczonymi $1\ldots N$ i $M$ krawędziami ($2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}$). Graf $G$ może zawierać pętle (krawędzie łączące wierzchołek z nim samym), ale nie zawiera krawędzi równoległych (wielu krawędzi łączących te same końce).

Dla każdego $1\le a\le N$ i $0\le b$ niech $f_G(a,b)$ będzie funkcją logiczną, która przyjmuje wartość prawda, jeśli istnieje droga z wierzchołka $1$ do wierzchołka $a$ przechodząca dokładnie przez $b$ krawędzi, a w przeciwnym razie przyjmuje wartość fałsz. Jeśli krawędź jest przemierzana wiele razy, jest liczona tyle samo razy.

Elsie chce naśladować Bessie. W szczególności chce skonstruować nieskierowany graf $G'$ taki, że $f_{G'}(a,b)=f_G(a,b)$ dla wszystkich $a$ i $b$.

Elsie chce wykonać jak najmniej pracy, dlatego chce skonstruować możliwie najmniejszy graf. Twoim zadaniem jest zatem obliczenie najmniejszej możliwej liczby krawędzi w $G'$.

Każde wejście zawiera $T$ ($1\le T\le 5\cdot 10^4$) przypadków testowych, które należy rozwiązać niezależnie. Gwarantowane jest, że suma $N$ dla wszystkich przypadków testowych nie przekracza $10^5$, a suma $M$ dla wszystkich przypadków testowych nie przekracza $2\cdot 10^5$.

Wejście

Pierwszy wiersz wejścia zawiera $T$, liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $N$ i $M$.

Każdy z kolejnych $M$ wierszy każdego przypadku testowego zawiera dwie liczby całkowite $x$ i $y$ ($1\le x\le y\le N$), oznaczające, że w $G$ istnieje krawędź między $x$ i $y$.

Dla czytelności kolejne przypadki testowe są oddzielone pustymi wierszami.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu najmniejszą możliwą liczbę krawędzi w $G'$.

Przykład

Wejście 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

Wyjście 1

4
5

Uwagi

W pierwszym przypadku testowym Elsie może skonstruować $G'$, zaczynając od $G$ i usuwając $(2,5)$. Może też skonstruować graf z następującymi krawędziami, ponieważ nie jest ograniczona jedynie do usuwania krawędzi z $G$:

1 2
1 4
4 3
4 5

Elsie z pewnością nie może uzyskać mniej niż $N-1$ krawędzi, ponieważ $G'$ również musi być spójny.

Wejście 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

Wyjście 2

10
11
15
18
22
26
31

Uwagi

W każdym z tych przypadków testowych Elsie nie może uzyskać lepszego wyniku niż Bessie.

Autor zadania: Benjamin Qi