У Беси есть связный ненаправленный граф G с n вершинами, помеченными 1..n и m ребрами. G может содержать петли (ребра из вершины в неё же), но не имеет параллельных ребер (несколько ребер, соединяющих одни и те же конечные точки).

Пусть fG(a, b) это булевская функция, которая отвечает истина, если существует путь от вершины 1 до вершины a, который проходит ровно b ребер, для 1 ≤ a ≤ n и 0 ≤ b и ложь иначе. Если по ребру проходим множество раз, это число включается в ответ.

Эльза хочет копировать Беси. В частности, она хочет сконструировать ненаправленный граф G′ такой, что fG′(a, b) = fG(a, b) для всех a и b.

Эльза хочет сделать минимальное количество работы, поэтому она хочет сконструировать минимально возможный граф. Ваша задача - вычислить минимально возможное количество ребер в G′.

Каждый ввод содержит t тестов, которые должны решаться независимо. Гарантируется, что сумма n по всем тестам не превысит 105, а сумма m по всем тестам не превысит 2 * 105.

Входные данные

Первая строка ввода содержит количество тестов t (1 ≤ t ≤ 5 * 104).

Первая строка каждого теста содержит два целых числа n и m (2 ≤ n ≤ 105, n − 1 ≤ m ≤ (n2 + n) / 2.

Следующие m строк каждого теста содержат два целых числа x и y (1 ≤ x ≤ y ≤ n), обозначающих ребро между x и y в G.

Последовательные тесты разделены пустой строй для читабельности.

Выходные данные

Для каждого теста выведите минимально возможное количество ребер в G′ в отдельной строке.

Пример

В первом тесте, Эльза может сконструировать G′, начав с G и удалив ребро (2, 5). Или может сконструировать граф со следующим ребрами

1 2
1 4
4 3
4 5

поскольку она не ограничена только удалением ребер из G: Эльза определенно не может сделать меньше чем n − 1 ребро, поскольку граф G′ также должен быть связным.