char s[1<<17];i,t,a,p,x,g;f(n){g=!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];p+=f(i),c=c*x*x*x*x*x%9)t+=s[i]-=48,a+=c*(~p?!p:3)*s[i],p-=f(strlen(++i+s)),c*=x;}