import sys

def main():
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    
    for s in cases:
        digits = [int(c) for c in s]
        m = len(digits)
        if m == 1:
            d = digits[0]
            if d == 0:
                print(0)
            else:
                mod = d % 9
                print(9 if mod == 0 else mod)
            continue
        
        n = m - 1
        prev_row = [1]
        for current_n in range(1, n+1):
            current_row = [1]
            for i in range(1, current_n):
                current_row.append((prev_row[i-1] + prev_row[i]) % 9)
            current_row.append(1)
            prev_row = current_row
        
        sum_mod = 0
        for i in range(m):
            sum_mod = (sum_mod + digits[i] * prev_row[i]) % 9
        
        any_non_zero = any(d != 0 for d in digits)
        if sum_mod == 0:
            print(9 if any_non_zero else 0)
        else:
            print(sum_mod)

if __name__ == '__main__':
    main()