У Бесі є зв'язний ненаправлений граф \(G\) з \(N\) вершинами, поміченими \(1\ldots N\) і \(M\) ребрами (\(2\le N\le 10^5, N-1\le M\le \frac{N^2+N}{2}\)). \(G\) може містити петлі (ребра з вершини в неї ж), але не має паралельних ребер (кілька ребер, що з'єднують одні й самі кінцеві точки).

Нехай \(f_G(a,b)\) це булева функція, яка відповідає істині, якщо існує шлях від вершини \(1\) до вершини \(a\), який проходить рівно \(b\) ребер, для \(1\le a\le N\) і \(0\le b\), і хибна інакше.

Якщо по ребру проходимо багато разів, це число включається у відповідь.

Ельза хоче копіювати Бесі. Зокрема, вона хоче сконструювати ненаправлений граф \(G'\) такий, що \(f_{G'}(a,b)=f_G(a,b)\) для всіх \(a\) і \(b\).

Ельза хоче зробити мінімальну кількість роботи, тому вона хоче сконструювати мінімально можливий граф. Ваше завдання – обчислити мінімально можливу кількість ребер у \(G'\).

Кожне введення містить \(T\) (\(1\le T\le 5\cdot 10^4\)) тестів, які мають вирішуватися незалежно. Гарантується, що сума \(N\) по всіх тестах не перевищить \(10^5\), а сума \(M\) по всіх тестах не перевищить \(2\cdot 10^5\).

Формат вхідних даних

Перший рядок введення містить \(T\) кількість тестів.

Перший рядок кожного тесту містить два цілих числа \(N\) та \(M\).

Наступні \(M\) рядків кожного тесту містять два цілих числа \(x\) і \(y\) (\(1\le x\le y\le N\)), що позначають ребро між \(x\) і \(y\) \(G\).

Послідовні тести розділені порожнім рядком для читабельності.

Формат вихідних даних

Для кожного тесту виведіть мінімально можливу кількість ребер \(G'\) на окремому рядку.

Приклад вхідних даних

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

Приклад вихідних даних

4
5

У першому тесті, Ельза може сконструювати \(G'\), почавши з \(G\) і видаливши ребро \((2,5)\). Або може сконструювати граф із наступними ребрами

1 2
1 4
4 3
4 5

Ельза не може зробити менше ніж \(N-1\) ребро, оскільки граф \(G'\) також має бути зв'язним.

Приклад вхідних даних

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

Приклад вихідних даних

10
11
15
18
22
26
31

У кожному з цих тестів, Ельза не може зробити краще, ніж Бесі.

ОЦІНЮВАННЯ:

• У всіх тестах введення 3 \(N\le 5\).
• У всіх тестах вводів 4-5 \(M=N\).
• У всіх тестах вводів 6-9, якщо це не випадок \(f_G(x,b)=f_G(y,b)\) для всіх \(b\), тоді існує таке \(b\) що \(f_G(x,b)\) істина, а \(f_G(y,b)\) брехня.
• У всіх тестах вводів 10-15 \(N\le 10^2\).
• У всіх тестах вводів 16-20 немає додаткових обмежень.