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