Ферма Farmer John состоит из $N$ полей $(1 \leq N \leq 10^5)$, для удобства пронумерованных $1 \ldots N$. Между этими полями есть $M$ двусторонних дорог $(0 \leq M \leq 10^5)$, каждая из которых соединяет пару полей.

На ферме есть два коровника: один на поле $1$, другой на поле $N$. Farmer John хочет обеспечить возможность пройти между двумя коровниками по некоторой последовательности дорог. Для достижения этой цели он готов построить не более двух новых дорог. Из-за расположения полей стоимость строительства новой дороги между полями $i$ и $j$ равна $(i-j)^2$.

Помогите Farmer John определить минимальную стоимость, необходимую для того, чтобы коровники $1$ и $N$ стали достижимы друг из друга.

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

Каждый входной тест содержит $T$ подтестов ($1\le T\le 20$), все из которых необходимо решить правильно, чтобы пройти этот входной тест.

Первая строка входных данных содержит $T$, после чего следуют $T$ подтестов.

Каждый подтест начинается с двух целых чисел $N$ и $M$. Затем следуют $M$ строк, каждая из которых содержит два целых числа $i$ и $j$, обозначающих дорогу между двумя различными полями $i$ и $j$. Гарантируется, что между любыми двумя полями есть не более одной дороги, а сумма $N+M$ по всем подтестам не превышает $5 \cdot 10^5$.

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

Выведите $T$ строк. В $i$-й строке должно находиться одно целое число — минимальная стоимость для $i$-го подтеста.

Примеры

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

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

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

2
1

Примечание

В первом подтесте оптимально соединить поля $2$ и $3$ одной дорогой, а поля $3$ и $4$ — другой.

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

Подзадачи

• Тест 2 удовлетворяет условию $N \le 20$.
• Тесты 3-5 удовлетворяют условию $N \le 10^3$.
• Тесты 6-10 не имеют дополнительных ограничений.

Автор задачи: Nick Wu