def count_factors_of_3(x):
    count = 0
    while x % 3 == 0 and x != 0:
        count += 1
        x = x // 3
    return count

def main():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    for s in cases:
        n = len(s)
        sum_mod = 0
        current_val = 1  # C(n-1, 0) starts as 1
        current_exp = 0
        for i in range(n):
            if i == 0:
                c = (current_val * (3 ** current_exp)) % 9
            else:
                numerator = (n - i)
                denominator = i
                num_3 = count_factors_of_3(numerator)
                den_3 = count_factors_of_3(denominator)
                current_exp += (num_3 - den_3)
                numerator_red = numerator // (3 ** num_3)
                denominator_red = denominator // (3 ** den_3)
                inv_denominator_red = pow(denominator_red, -1, 9)
                current_val = (current_val * numerator_red) % 9
                current_val = (current_val * inv_denominator_red) % 9
                if current_exp >= 2:
                    c = 0
                else:
                    c = (current_val * (3 ** current_exp)) % 9
            digit = int(s[i])
            sum_mod = (sum_mod + digit * c) % 9
        if sum_mod == 0:
            has_non_zero = any(c != '0' for c in s)
            print(9 if has_non_zero else 0)
        else:
            print(sum_mod)

if __name__ == "__main__":
    main()