Ферма Джона состоит из множества n полей, последовательно пронумерованных 1..n. Между этими полями имеется m (0 ≤ m ≤ 105) двунаправленных дорожек, соединяющих пары полей.

На этой ферме имеется два амбара - один в поле 1, другой в поле n. ФД хочет быть уверен, что имеется путь между двумя амбарами последовательностью дорожек. Оно готов построить до двух новых дорожек, чтобы добиться своей цели. Стоимость построения дорожки между полями i и j есть (i − j) ^ 2.

Помогите ФД определить минимальную стоимость сделать так, чтобы амбары 1 и n стали достижимы друг для друга.

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

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

Каждый тест начинается с двух целых чисел n (1 ≤ n ≤ 105) и m. Каждая из последующих m строк содержит два целых числа i и j, означающих путь между двумя различными полями i и j. Гарантируется, что имеется не более одного пути между любыми двумя полями. и что сумма n + m для всех подтестов не более 5 * 105.

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

Выведите t строк. i-ая строка должна содержать одно целое число - минимальную стоимость для i-го теста.

Пример

В первом тесте оптимально соединить поля 2 и 3, а также поля 3 и 4.

Во втором тесте оптимально соединить поля 3 и 4. Второй путь не требуется.