#include<iostream>
using namespace std;
#define  MAXN 1001
int T,a,b,c,d,e,f,g,h,i,dp[MAXN];
int Mod(int m,int n)
{
	int t=m%n;
	if(t<0)return t+n;
	else return t;
}
int F(int x)
{
	if(x==0)return a;
	if(x==1)return b;
	if(x==2)return c;
	if(dp[x-1]==-1)dp[x-1]=F(x-1);
	if(dp[x-2]==-1)dp[x-2]=F(x-2);
	if(dp[x-3]==-1)dp[x-3]=F(x-3);
	if(x%2)	return Mod(d*dp[x-1]+e*dp[x-2]-f*dp[x-3],g);
	return Mod(f*dp[x-1]-d*dp[x-2]+e*dp[x-3],h);
}
int main()
{
	cin>>T;
	while(T--)
	{
		fill(dp,dp+MAXN,-1);
		cin>>a>>b>>c>>d>>e>>f>>g>>h>>i;
		cout<<F(i)<<endl;
	}	
}