#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=(k);++i)
#define drp(i,j,k) for(int i=j;i>=(k);--i)
#define MAXN 105
typedef long long ll;
typedef __int128 i128;
inline int read(){
	int x=0;
	bool sgn=true;
	char ch=getchar();
	while(!isdigit(ch)) sgn^=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return sgn?x:-x;
}
inline void chkmin(int &x,int y){x=std::min(x,y);}
int n,m,a[MAXN][MAXN][MAXN],dis[MAXN][MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN];
const int dx[6]={1,-1,0,0,0,0};
const int dy[6]={0,0,1,-1,0,0};
const int dz[6]={0,0,0,0,1,-1};
inline int solve(){
	int x1=read(),y1=read(),z1=read();
	int x2=read(),y2=read(),z2=read();
	if(a[x1][y1][z1]) return -1;
	std::queue<int> q;
	memset(vis,0,sizeof(vis));
	q.push(x1*1000000+y1*1000+z1);
	dis[x1][y1][z1]=0;
	vis[x1][y1][z1]=true;
	while(!q.empty()){
		int x=q.front()/1000000,y=q.front()/1000%1000,z=q.front()%1000;
		q.pop();
		rep(i,0,5){
			int tx=x+dx[i],ty=y+dy[i],tz=z+dz[i];
			if(tx<1||tx>n||ty<1||ty>n||tz<1||tz>n||vis[tx][ty][tz]||a[tx][ty][tz]) continue;
			vis[tx][ty][tz]=true,dis[tx][ty][tz]=dis[x][y][z]+1,q.push(tx*1000000+ty*1000+tz);
		}
	}
	return vis[x2][y2][z2]?dis[x2][y2][z2]:-1;
}
int main(){
	drp(task,read(),1){
		n=read(),m=read(),memset(a,0,sizeof(a));
		while(m--){
			int l1=read(),l2=read(),l3=read();
			int r1=read(),r2=read(),r3=read();
			rep(i,l2,r2) rep(j,l3,r3) ++a[l1][i][j];
			rep(i,l2,r2) rep(j,l3,r3) --a[r1+1][i][j];
		}
		rep(i,1,n) rep(j,1,n) rep(k,1,n) a[i][j][k]+=a[i-1][j][k];
		printf("%d\n",solve());
	}
}