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;}}}