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