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$이다.

헛간 $1$과 $N$이 서로 도달 가능하도록 하는 데 필요한 최소 비용을 구하여 Farmer John을 도와라.

입력

각 입력 테스트 케이스에는 $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