Beyond the Void

/* 
 * Problem: POI1997 ali
 * Author: Guo Jiabao
 * Time: 2008.11.28 20:42:00
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
 
using namespace std;
 
struct coins
{
	int a,b,c,step;
};
 
class tQueue
{
	public:
		class tList
		{
			public:
				tList *next;
				coins v;
				tList(coins tv): v(tv)
				{
					next=0;
				}
		};
		tList *first,*last;
		int Size;
		tQueue()
		{
			Size=0;
			first=last=0;
		}
		void ins(coins v)
		{
			if (first)
				last=last->next=new tList(v);
			else
				first=last=new tList(v);
			Size++;
		}
		coins pop()
		{
			Size--;
			tList *t=first;
			coins r=t->v;
			first=first->next;
			delete t;
			return r;
		}
		void reset()
		{
			tList *t;
			while (first)
			{
				t=first;
				first=first->next;
				delete t;
			}
			first=last=0;
		}
};
 
struct pri
{
	coins A,B;
};
 
const int LIM=100;
 
tQueue Q;
coins S,T;
pri P[11];
int N,M;
bool Hash[100][100][100];
 
void init()
{
	freopen("ali.in","r",stdin);
	freopen("ali.out","w",stdout);
	scanf("%d",&M);
}
 
void readfile()
{
	int i;
	scanf("%d%d%d%d%d%d",&S.a,&S.b,&S.c,&T.a,&T.b,&T.c);
	S.step=0;
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d%d%d%d%d",&P[i].A.a,&P[i].A.b,&P[i].A.c,&P[i].B.a,&P[i].B.b,&P[i].B.c);
	}
}
 
int solve()
{
	int k;
	coins i,j;
	if (S.a==T.a && S.b==T.b && S.c==T.c)
		return 0;
	Q.reset();
	memset(Hash,0,sizeof(Hash));
	Q.ins(S);
	Hash[S.a][S.b][S.c]=true;
	while (Q.Size)
	{
		i=Q.pop();
		j.step=i.step+1;
		for (k=1;k<=N;k++)
		{
			if (i.a >= P[k].A.a && i.b >= P[k].A.b && i.c >= P[k].A.c)
			{
				j.a=i.a-P[k].A.a+P[k].B.a;
				j.b=i.b-P[k].A.b+P[k].B.b;
				j.c=i.c-P[k].A.c+P[k].B.c;
				if (j.a>=T.a && j.b>=T.b && j.c>=T.c)
					return j.step;
				if (j.a>=LIM || j.b>=LIM || j.c>=LIM) continue;
				if (!Hash[j.a][j.b][j.c])
				{
					//printf("[%d,%d,%d] => [%d,%d,%d]n",i.a,i.b,i.c,j.a,j.b,j.c);
					Hash[j.a][j.b][j.c]=true;
					Q.ins(j);
				}
			}
		}
	}
	return -1;
}
 
int main()
{
	int i,Ans;
	init();
	for (i=1;i<=M;i++)
	{
		readfile();
		Ans=solve();
		if (Ans==-1)
			printf("NIEn");
		else
			printf("%dn",Ans);
	}
	return 0;
}