import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().run(); } int[] toint(char[] cs) { int[] ret=new int[cs.length]; for(int i=0;i0;n>>=1,a=a*a%9)if(n%2==1)ret=ret*a%9; return ret; } int inv(int a) { if(a%3==0)throw new AssertionError(); return pow(a%9,5); } int count3(int a) { int ret=0; while(a%3==0) { a/=3; ++ret; } return ret; } int mul(int...a) { int r=1; for(int v:a)r=(int)((long)r*v%9); return r; } void run() { Scanner sc=new Scanner(System.in); int T=sc.nextInt(); while(T-->0) { int[] a=toint(sc.next().toCharArray()); int n=a.length; int binom=1; int c3=0; int ans=0; boolean zero=Arrays.stream(a).filter(v->v==0).count()==n; for(int i=0;i