import sys

def main():
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    for s in cases:
        n = len(s)
        if n == 1:
            print(s[0])
            continue
        
        mod = 9
        dp = [0] * n
        dp[0] = 1
        for i in range(n-1):
            new_dp = [0] * (i + 2)
            new_dp[0] = 1
            new_dp[-1] = 1
            for j in range(1, i + 1):
                new_dp[j] = (dp[j-1] + dp[j]) % mod
            dp = new_dp
        
        total = 0
        for i in range(n):
            total = (total + int(s[i]) * dp[i]) % mod
        
        if total == 0:
            if any(c != '0' for c in s):
                print(9)
            else:
                print(0)
        else:
            print(total)

if __name__ == "__main__":
    main()