y,i,t,a,b,m,s,c,p,x;f(n){return!n|n%3?y=n%9,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*y*y*y*y*y%9;}