use fio::*;

const INV_9: [u8; 9] = [0, 1, 5, 0, 7, 2, 0, 4, 8];

fn solve(mut rng: impl ExactSizeIterator<Item = u8>) -> u8 {
    let n = rng.len();
    let mut upper_mod_9 = 1;
    let mut upper_pow_3 = 0;
    let mut lower_mod_9 = 1;
    let mut lower_pow_3 = 0;

    let split = |mut x: usize| -> (u8, usize) {
        let mut pow_3 = 0;
        while x % 3 == 0 {
            x /= 3;
            pow_3 += 1;
        }
        ((x % 9) as u8, pow_3)
    };

    let augment = |mod9: &mut u8, pow_3: &mut usize, x: usize| {
        let (x_mod_9, x_pow_3) = split(x);
        *mod9 *= x_mod_9;
        *mod9 %= 9;
        *pow_3 += x_pow_3;
    };

    let v = rng.next().unwrap();
    let mut is_ans_0 = v == 0;
    let mut ans = v % 9;

    for i in 1..=n - 1 {
        augment(&mut upper_mod_9, &mut upper_pow_3, n - i);
        augment(&mut lower_mod_9, &mut lower_pow_3, i);
        let v = rng.next().unwrap();

        if v != 0 {
            is_ans_0 = false;
        }

        let mut m9 = upper_mod_9 * INV_9[lower_mod_9 as usize] % 9;
        let p3 = upper_pow_3 - lower_pow_3;

        if p3 == 1 {
            m9 = m9 * 3 % 9;
        }
        if p3 <= 1 {
            ans = (ans + v * m9) % 9;
        }
    }

    if is_ans_0 {
        0
    } else if ans == 0 {
        9
    } else {
        ans
    }
}

fn main() {
    let t = read();
    for _ in 0..t {
        let s = read_line();
        println!(
            "{}",
            solve(
                s.chars()
                    .collect::<Vec<_>>()
                    .into_iter()
                    .map(|x| x.to_digit(10).unwrap() as u8)
            )
        );
    }
}

mod fio {
    use std::{
        cell::RefCell,
        convert::TryInto,
        fmt::Debug,
        io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout},
        str::FromStr,
    };
    thread_local! {
        pub static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
        pub static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
    }

    #[allow(dead_code)]
    pub fn read<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        read_line().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn read_vec<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn read_tuple<T, const N: usize>() -> [T; N]
    where
        T: FromStr + Debug,
        <T as FromStr>::Err: Debug,
    {
        read_vec::<T>().try_into().unwrap()
    }

    /// whitespace at the end of the line is ignored
    pub fn read_line() -> String {
        let mut s = String::new();
        STDIN.with(|cell| {
            cell.borrow_mut().read_line(&mut s).unwrap();
        });
        String::from_str(s.trim_end()).unwrap()
    }
}

#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell|{
            use std::io::Write;
            write!(cell.borrow_mut(), $($t)*).unwrap()
        })};
}

#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            writeln!(cell.borrow_mut(), $($t)*).unwrap()
        })
    };
}

#[macro_export]
macro_rules! flush {
    () => {
        fio::STDOUT.with(|cell| {
            use std::io::Write;
            cell.borrow_mut().flush().unwrap()
        });
    };
}