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