#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 105;
const int inf  = 1e9;

int n,m;
int a[maxn][maxn][maxn],d[maxn][maxn][maxn];
int xi[3][2];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>m;
		memset(a,0,sizeof a);
		memset(d,-1,sizeof d);
		while(m--)
		{
			for(int j=0;j<2;j++) 
			{
				for(int i=0;i<3;i++) cin>>xi[i][j];
			}
			for(int i=0;i<3;i++) xi[i][1]++;
			
			for(int j1=0,s1=1;j1<2;j1++,s1=-s1) for(int j2=0,s2=1;j2<2;j2++,s2=-s2) 
			for(int j3=0,s3=1;j3<2;j3++,s3=-s3)
			{
				a[ xi[0][j1] ][ xi[1][j2] ][ xi[2][j3] ]+= s1*s2*s3;
			}
		}
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
		{
			a[i][j][k]+=a[i][j][k-1];
		}
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
		{
			a[i][j][k]+=a[i][j-1][k];
		}
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++)
		{
			a[i][j][k]+=a[i-1][j][k];
		}
		
		for(int j=0;j<2;j++) 
		{
			for(int i=0;i<3;i++) cin>>xi[i][j];
		}
		d[ xi[0][0] ][ xi[1][0] ][ xi[2][0] ]=0;
		queue< tuple<int,int,int> >q;
		q.emplace( xi[0][0], xi[1][0], xi[2][0] );
		while(!q.empty())
		{
			const auto [x,y,z]= q.front(); q.pop();
			for(int dx=-1;dx<=1;dx++) for(int dy=-1;dy<=1;dy++) for(int dz=-1;dz<=1;dz++)
			{
				int cnt= (dx==0) + (dy==0) + (dz==0);
				if( cnt==2 )
				{
					int nx=x+dx, ny=y+dy, nz=z+dz;
					if( a[nx][ny][nz]==0 && d[nx][ny][nz]==-1 && nx>=1 && nx<=n && ny>=1 && ny<=n && nz>=1 && nz<=n )
					{
						d[nx][ny][nz]= d[x][y][z]+1;
						q.emplace( make_tuple(nx,ny,nz) );
					}
				}
			}
		}
		cout<<d[ xi[0][1] ][ xi[1][1] ][ xi[2][1] ]<<'\n';
	}
	
	return 0;
}