from ctypes import * #MacOSX #libc=CDLL("libSystem.B.dylib") #Linux libc = CDLL("libc.so.6") printf = libc.printf scanf = libc.scanf #!/usr/bin/env python3 num_idx=[0,0,1,0,2,5,0,4,3,0] two_idx=[1,2,4,8,7,5] t=c_int() scanf(b"%d",byref(t)) buf=(c_char* 2000001)() for loop in range(t.value): scanf(b"%s",byref(buf)) s=str(buf.value.decode('utf-8')) n=len(s) allzero=True for i in range(n): if s[i]!='0': allzero=False if allzero: print("0") continue ans=0 num=n-1 den=1 two=0 three=0 for i in range(n): if three<=1: cur=int(s[i]); cur=cur*two_idx[two%6] if three==1: cur*=3 ans+=cur; if i==n-1: break; tmp=num; while tmp%3==0: tmp/=3 three+=1 two+=(num_idx[int(tmp%9)]); tmp=den; while tmp%3==0: tmp/=3 three-=1; two+=(6-num_idx[int(tmp%9)]); num-=1 den+=1 ans%=9 if ans ==0: ans=9; printf(b"%d\n",ans);