> #include <stdio.h>
> int a,b,c,d,e,f,g,h;
> int function(int i)
> {
> 	int result;
> 	if (i==0) result=a;return result;
> 	if (i==1) result=b;return result;
> 	if (i==2) result=c;return result;
> 	if (i>=3 && (i%2)==0) 
> 	{
> 		result=d*function(i-1)+e*function(i-2)-f*function(i-3)%g;
> 		return result;
> 	}
> 	if (i>=3 && (i%2)==1)
> 	{
> 		result=f*function(i-1)-d*function(i-2)+e*function(i-3)%h;
> 		return result;
> 	}
> }
> 
> void main()
> {
> 	int n,k,i,s;
> 	scanf("%d",&n);
> 	for (k=1;k<=n;k++)
> 	{
> 		scanf("%d %d %d %d %d %d %d %d %d",&a,&b,&c,&d,&e,&f,&g,&h,&i);
> 		s=function(i);
> 	printf("%d\n",s);
> 	}
> }