最近，Zayin 迷上了一款名为《明日方舟》（Arknights）的塔防游戏。其中最特别的关卡是第四章的第五关：Don’t panic。这一关最独特的地方在于，敌人在经过源石地板时会持续受到真实伤害。作为世界上最帅的男人，他尝试在不同的位置放置障碍物，试图让所有敌人在到达终点前被消灭。经过多次尝试，他终于获得了三星通关评价。

有趣的是，那天晚上 Zayin 梦见自己变成了碎骨（King Slayer，敌方首领）。在梦中，塔防游戏的地图变成了一个边长为 $n$ 的立方体。Zayin 每秒可以从当前位置向前、向后、向上、向下、向左或向右移动一步，但不能走出地图范围，也不能穿过有障碍物的格子。

和原游戏一样，想要消灭所有敌人的玩家可以多次放置障碍物。具体来说，在梦中，玩家每次可以在满足 $a \le x \le d$，$b \le y \le e$，$c \le z \le f$ 的所有坐标 $(x, y, z)$ 处放置障碍物（如果该位置尚未有障碍物）。

现在，Zayin 知道玩家会放置 $m$ 次障碍物，并且知道每次放置的位置。为了避免在途中死亡，Zayin 想尽快到达终点。但不幸的是，Zayin 迷路了太久，以至于所有的障碍物都已经放置完毕。现在，Zayin 向你求助。你能帮他以最快的速度走出地图吗？

输入格式

第一行包含一个整数 $T(1 \le T \le 5)$，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，其中 $n$ 是地图的大小，$m$ 是玩家放置障碍物的次数。$(1 \le n \le 100, 1 \le m \le 1000)$

接下来的 $m$ 行，每行包含六个整数 $a, b, c, d, e, f$，表示玩家放置障碍物的范围。$(1 \le a \le d \le n, 1 \le b \le e \le n, 1 \le c \le f \le n)$

最后一行包含六个整数 $x_1, y_1, z_1, x_2, y_2, z_2$。前三个整数表示 Zayin 当前的位置，后三个整数表示终点的位置。

输出格式

对于每个测试用例，输出一行一个整数，表示 Zayin 到达终点所需的最少秒数。如果 Zayin 无法到达终点，则输出 $-1$。

样例

输入 1

3
3 0
3 1
2 1 1 2 3 3
1 1 1 3 3 3
3 3
2 1 1 2 2 3
1 1 2 2 3 2
1 2 2 3 3 2
1 1 1 1 1 3

输出 1

6
-1
14