char s[1<<17];i,t,a,p,x;f(n){return!n|n%3?x=n%9,0:f(n/3)+1;}main(c){for(gets(s);gets(s);t=a=p=i=!printf("%d\n",a%9?:t?9:0))for(c=1;s[i];c=c*x*x*x*x*x%9)t+=s[i]-=48,a+=c*(p-1?!p:3)*s[i],p+=f(strlen(++i+s)),c*=x,p-=f(i);}