y,i,t,a,b,m,s,c,p,x;v[]={0,1,5,0,7,2,0,4,8};f(n){return!n|n%3?y=n,0:f(n/3)+1;}main(n){for(gets(&c);y=~scanf("%d%d%d%d%d",&n,&x,&a,&b,&m);t=s=p=i=!printf("%d\n",s%9?:t?9:0)){for(c=1;n--;x=((x^a)+b)%m){t+=x%10;s+=c*(p-1?!p:3)*(x%10)%9;p+=f(n);c*=y;p-=f(++i);c=c*v[y%9]%9;}}}