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