#include <bits/stdc++.h> using namespace std; pair<long long, long long> extgcd(long long a, long long b) { if (b == 0) return{ 1, 0 }; long long x, y; tie(x, y) = extgcd(b, a % b); return{ y, x - a / b * y }; } long long modulo(long long a, long long mod) { return (a % mod + mod) % mod; } long long modinv(long long a, long long mod) { return modulo(extgcd(a, mod).first, mod); } map<long long, long long> prime_factors(long long n) { map<long long, long long> ret; for (long long i = 2; i * i <= n; i++) while (n % i == 0) ret[i]++, n /= i; if (n != 1) ret[n]++; return ret; } struct Combination { struct CombinationLucas { long long p, q; long long mod; vector<long long> power; vector<long long> F, invF; vector<int> e; CombinationLucas(int n, long long p, long long q) : p(p), q(q), F(n), invF(n), e(n), power(q + 1) { mod = 1; for (int i = 0; i < q; i++) { mod *= p; } power[0] = 1; for (int i = 1; i <= q; i++) { power[i] = power[i - 1] * p % mod; } F[0] = 1; for (long long i = 1; i < n; i++) { if (i % p == 0) { F[i] = F[i - 1]; } else { F[i] = F[i - 1] * i % mod; } } invF[n - 1] = modinv(F[n - 1], mod); for (long long i = n - 2; i >= 0; i--) { if ((i + 1) % p == 0) { invF[i] = invF[i + 1]; } else { invF[i] = invF[i + 1] * (i + 1) % mod; } } for (int i = 1; i < n; i++) { F[i] = F[i] * F[i / p] % mod; invF[i] = invF[i] * invF[i / p] % mod; e[i] = i / p + e[i / p]; } } long long operator()(int n, int r) { if (n < 0 || r < 0 || n < r) return 0; long long result = F[n] * invF[n - r] % mod * invF[r] % mod; result = result * power[min<int>(q, e[n] - e[n - r] - e[r])] % mod; return result; } }; vector<long long> inv; vector<CombinationLucas> cs; Combination(int n, long long mod) { auto pf = prime_factors(mod); for (auto kv : pf) { cs.emplace_back(n, kv.first, kv.second); } long long m = 1; for (auto &c : cs) { inv.push_back(modinv(m, c.mod)); m *= c.mod; } } long long operator()(int n, int r) { long long x = 0; long long mod = 1; for (int i = 0; i < cs.size(); i++) { long long y = cs[i](n, r); x += mod * (y - x) * inv[i]; mod *= cs[i].mod; x %= mod; } return (x % mod + mod) % mod; } }; int main() { int T; cin >> T; Combination cb(101010, 9); while (T--) { string s; cin >> s; int n = s.size(); long long ans = 0; for (int i = 0; i < n; i++) { (ans += cb(n - 1, i) * (s[i] - '0')) %= 9; } if (ans == 0) ans = 9; if (count(s.begin(), s.end(), '0') == n) ans = 0; printf("%lld\n", ans); } }