#include #define _overload(_1,_2,_3,name,...) name #define _rep(i,n) _range(i,0,n) #define _range(i,a,b) for(int i=int(a);i=int(b);--i) #define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__) using namespace std; const int limit=100000; int divisor[limit+1],prime[limit+1]; int factor[limit+1][10]; void init(){ int total=0; for(int i=2;i<=limit;++i) divisor[i]=i; for(int p=2;p<=limit;++p){ if(divisor[p]==p) prime[total++]=p; for(int i=0;i>=1; } return b; } const int t_limit=10000; const int n_limit=10000; int main(void){ init(); int t=0,all=0; scanf("%d",&t); assert(1<=t&&t<=t_limit); rep(loop,t){ char s[limit+1]; scanf("%s",s); int n=strlen(s); assert(1<=n); all+=n; bool allzero=true; rep(i,n) if(s[i]!='0') allzero=false; if(allzero){ puts("0"); continue; } int ans=0,f[10]; fill(f,f+10,0); int num=n-1,den=1; rep(i,n){ int cur=s[i]-'0'; rep(j,10) cur=(cur*power(j,f[j],9))%9; ans=(ans+cur)%9; rep(j,10) f[j]+=factor[num][j]; rep(j,10) f[j]-=factor[den][j]; num--,den++; } if(ans==0) ans=9; printf("%d\n",ans); } assert(all<=n_limit); return 0; }