Recently, Zayin became obsessed with a tower defense game called Arknights. The most special level is the 5th level of chapter 4: Don’t panic. The most special thing about this level is that an enemy will continue taking radioactive damage after passing through the Active Originiums. As the most handsome man in the world, he tried to put obstacles in various positions, making all the enemies to be killed before reaching the end. After many attempts, he finally won the three stars clearance award.
Interestingly, that night Zayin dreamt that he had become the King Slayer (the leader of enemies). In the dream, the map of the tower defense game becomes a cube with edge length $n$. Zayin can take a step forward, backward, up, down, left or right from his current position every second, but can’t get out of the map or walk through a grid of obstacles.
As in the original game, the player, who wants to kill all the enemies, can put obstacles many times. In particular, in the dream, every time players can place obstacles at all the coordinates $(x,y,z)$ which satisfies $a \leq x \leq d$, $b \leq y \leq e$, $ c \leq z \leq f$, and has no obstacles yet.
Now, Zayin knows that the player will place obstacles $m$ times and the locations of each time. In order to avoid dying on the way, Zayin wants to go to the end as fast as possible. But unfortunately, Zayin got lost for so long that all the obstacles were placed. Now, Zayin asks you for help. Can you help him get out of the map as quickly as possible?
The first line of input contains an integer $T (1 \leq T \leq 5)$, denoting the number of test cases.
Each test case starts with two integers $n$ and $m$ in a line, where $n$ is the size of the map and $m$ is the number of times the player puts obstacles. $(1 \leq n \leq 100, 1 \leq m \leq 1000)$
The next $m$ lines contain six integers $a,b,c,d,e,f$ in each line, denoting the range of obstacles the player puts. $(1 \leq a \leq d \leq n, 1 \leq b \leq e \leq n, 1 \leq c \leq f \leq n)$
Then there are six integers $x_1,y_1,z_1,x_2,y_2,z_2$. The first three integers represent where Zayin is now, and the last three integers represent where the end point is.
For each testcase, output an integer in a line, denoting how many seconds at least Zayin need to go to the end. If Zayin can’t go to the end, output $-1$.
1 1 1 3 3 3
2 1 1 2 3 3
1 1 1 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
给定一个$n\times n \times n(n \leq 100)$的立方矩阵地图，其中有$m$个从$(a_i,b_i,c_i)$到$(d_i,e_i,f_i)$的长方体障碍物，给定起点$(x_1,y_1,z_1)$和终点$(x_2,y_2,z_2)$。求路径长度。