#include "stdio.h"
int a,b,c,d,e,f,g,h;
int Fun(int n)
{
      int f1,f2,f3,temp,i;
      switch(n)
      {
            case 0:return a;
            case 1:return b;
            case 2:return c;
            default:
                  {
                        f1=c,f2=b,f3=a;
                        for(i=3;i<=n;i++)
                        {
                              if(i%2==1) f3=((d*f1+e*f2-f*f3)%g+g)%g;
                              else f3=((f*f1-d*f2+e*f3)%h+h)%h;
                              temp=f3;
                              f3=f2;
                              f2=f1;
                              f1=temp;      
                        }
                        return temp;
                  }     
      }      
}

int main()
{
      int N;
      int i,j;
      scanf("%d",&N);
      for(j=0;j<N;j++)
      {
            scanf("%d%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h,&i);
            printf("%d\n",Fun(i));     
      }
      return 0;     
}