Doran 和 Krug 正在一个由 $(n + 1) \times (n + 1)$ 个单元格组成的网格上玩游戏，单元格的坐标为介于 $0$ 到 $n$ 之间（包含边界）的整数对。Krug 的目标是尽可能长时间不被 Doran 抓住，而 Doran 的目标是尽可能早地抓住 Krug。如果他们站在同一个网格单元格上，我们就说 Doran 抓住了 Krug。

游戏开始后，Krug 和 Doran 轮流行动，由 Krug 先手：

• Krug 可以选择留在同一个单元格，或者移动到垂直或水平相邻（但不能对角线相邻）的单元格。正式地，如果 Krug 当前位于单元格 $(a, b)$，她可以留在 $(a, b)$，或者移动到 $(a - 1, b)$、$(a, b - 1)$、$(a, b + 1)$、$(a + 1, b)$ 之一。
• Doran 可以选择留在同一个单元格，或者移动到垂直、水平或对角线相邻的单元格。正式地，如果 Doran 当前位于单元格 $(c, d)$，他可以留在 $(c, d)$，或者移动到 $(c - 1, d - 1)$、$(c - 1, d)$、$(c - 1, d + 1)$、$(c, d - 1)$、$(c, d + 1)$、$(c + 1, d - 1)$、$(c + 1, d)$、$(c + 1, d + 1)$ 之一。
• 两位玩家都不能移动到网格之外。

展示 Krug 和 Doran 可能移动方式的图示。字母 'K' 和 'D' 分别代表 Krug 和 Doran 的当前位置，有颜色的单元格代表每位玩家在各自回合中可以移动到的可能位置。

在给定玩家初始单元格的情况下，Krug 的生存时间定义为：直到 Doran 抓住 Krug 为止，Doran 进行的回合数。假设两位玩家都采取最优策略，求 Krug 的生存时间，或者在 Krug 可以无限生存时报告。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来的内容是测试用例的描述。

每个测试用例仅包含一行，其中有五个整数 $n, r_K, c_K, r_D$ 和 $c_D$ ($1 \le n \le 10^9$, $0 \le r_K, c_K, r_D, c_D \le n$, $(r_K, c_K) \ne (r_D, c_D)$) —— 其中 $n$ 是网格的大小，$(r_K, c_K)$ 代表 Krug 的起点单元格，$(r_D, c_D)$ 代表 Doran 的起点单元格。

输出格式

对于每个测试用例，输出在两位玩家都采取最优策略时 Krug 的生存时间。如果 Krug 可以无限生存，则输出 $-1$。

样例

输入样例 1

7
2 0 0 1 1
3 1 1 0 1
1 1 0 0 1
6 1 3 3 2
9 4 1 4 2
82 64 2 63 2
1000000000 500000000 500000000 1000000000 0

输出样例 1

1
3
1
4
2
19
1000000000

说明

第一个测试用例的解释：

Krug 起始于 $(0, 0)$，Doran 起始于 $(1, 1)$。在 Krug 的回合中，她只能移动到 $(0, 0)$、$(0, 1)$ 或 $(1, 0)$。

从 $(1, 1)$ 出发的 Doran 可以在单次移动中到达 $3 \times 3$ 网格上的任意单元格。因此，无论 Krug 移动到哪里，Doran 总能在他的第一个回合移动到她所在的单元格。Krug 的生存时间为 $1$。

第二个测试用例的解释：

Krug 起始于 $(1, 1)$，Doran 起始于 $(0, 1)$。为了在 Doran 的第一个回合中存活，Krug 必须移动到一个 Doran 无法到达的单元格。唯一符合条件的单元格是 $(2, 1)$。

在 Krug 移动到 $(2, 1)$ 后，Doran 移动到 $(1, 1)$ 以拉近距离。

现在，在她的第二次移动中，Krug 必须再次移动到一个 Doran 无法到达的单元格，即 $(3, 1)$。然后 Doran 移动到 $(2, 1)$。

此时，无论 Krug 在她的第三个回合移动到哪里，Doran 总能到达她所在的单元格。可以证明，这对双方来说都是最优策略，因此 Krug 的生存时间为 $3$。