import java.io.*;
import java.util.*;

public class yukicoder466 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Printer pr = new Printer(System.out);

		final int num_idx[]={0,0,1,0,2,5,0,4,3,0};
		final int two_idx[]={1,2,4,8,7,5};

		int t = sc.nextInt();
		
		for(;t>0;--t){
			String s=sc.next();
			int n=s.length();
	        
	        boolean allzero=true;
	        for(int i=0;i<n;++i) if(s.charAt(i)!='0') allzero=false;
	        
	        if(allzero){
	        	pr.println("0");
	            continue;
	        }

	        int ans=0,num=n-1,den=1,two=0,three=0,tmp;

	        for(int i=0;i<n;++i){
	            if(three<=1){
	                int cur=s.charAt(i)-'0';
	                cur=cur*two_idx[two%6]*(three==1?3:1);
	                ans+=cur;
	            }
	            
	            if(i==n-1) break;

	            tmp=num;
	            while(tmp%3==0){
	            	tmp/=3;three++;
	            }
	            two+=(num_idx[tmp%9]);
	            
	            tmp=den;
	            while(tmp%3==0){
	            	tmp/=3;three--;
	            }
	            two+=(6-num_idx[tmp%9]);
	            
	            num--;den++;
	        }

	        ans%=9;
	        if(ans==0) ans=9;
	       	pr.println(ans);
		}

		pr.close();
        sc.close();
    }

	@SuppressWarnings("unused")
	private static class Scanner {
		BufferedReader br;
		Iterator<String> it;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() throws RuntimeException  {
			try {
				if (it == null || !it.hasNext()) {
					it = Arrays.asList(br.readLine().split(" ")).iterator();
				}
				return it.next();
			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		int nextInt() throws RuntimeException {
			return Integer.parseInt(next());
		}

		long nextLong() throws RuntimeException {
			return Long.parseLong(next());
		}

		float nextFloat() throws RuntimeException {
			return Float.parseFloat(next());
		}

		double nextDouble() throws RuntimeException {
			return Double.parseDouble(next());
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new IllegalStateException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}