#include <bits/stdc++.h>
using namespace std;

struct CombinationAnyMod {
	struct CombinationPrimePower {
		int p, q;
		int mod;
		vector<int> F, invF, power, e;

		static pair<int, int> extgcd(int a, int b) {
			if (b == 0) return make_pair(1, 0);
			int x, y;
			tie(x, y) = extgcd(b, a % b);
			return make_pair(y, x - a / b * y);
		}

		static int modulo(int a, int mod) {
			return (a %= mod) < 0 ? a + mod : a;
		}

		static int modinv(int a, int mod) {
			return modulo(extgcd(a, mod).first, mod);
		}

		int mul(int x, int y) {
			return int64_t(x) * y % mod;
		}

		CombinationPrimePower(int n, int p, int 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] = mul(power[i - 1], p);

			F[0] = 1;
			for (int i = 1; i < n; i++) {
				F[i] = mul(F[i - 1], i % p == 0 ? 1 : i);
			}

			invF[n - 1] = modinv(F[n - 1], mod);
			for (int i = n - 2; i >= 0; i--) {
				invF[i] = mul(invF[i + 1], (i + 1) % p == 0 ? 1 : i + 1);
			}

			for (int i = 1; i < n; i++) {
				F[i] = mul(F[i], F[i / p]);
				invF[i] = mul(invF[i], invF[i / p]);
				e[i] = i / p + e[i / p];
			}
		}

		int operator()(int n, int r) {
			if (n < 0 || r < 0 || n < r) return 0;
			int f = mul(F[n], mul(invF[n - r], invF[r]));
			return mul(f, power[min(q, e[n] - e[n - r] - e[r])]);
		}
	};

	map<int, int> prime_factors(int n) {
		map<int, int> res;
		for (int i = 2; i * i <= n; i++) {
			for (; n % i == 0; n /= i) res[i]++;
		}
		if (n != 1) res[n] = 1;
		return res;
	}

	vector<CombinationPrimePower> cs;
	vector<int> inv;

	CombinationAnyMod(int n, int mod) {
		for (auto kv : prime_factors(mod)) {
			cs.emplace_back(n, kv.first, kv.second);
		}
		int m = 1;
		for (auto &c : cs) {
			inv.push_back(CombinationPrimePower::modinv(m, c.mod));
			m *= c.mod;
		}
	}

	int operator()(int n, int r) {
		int x = 0;
		int mod = 1;
		for (int i = 0; i < cs.size(); i++) {
			int y = cs[i](n, r);
			x += int64_t(y + cs[i].mod - x) * inv[i] % cs[i].mod * mod;
			mod *= cs[i].mod;
		}
		return x;
	}
};

int main() {
	int T;
	cin >> T;

	CombinationAnyMod cb(101010, 9);

	while (T--) {
		string s;
		cin >> s;

		int n = s.size();

		int 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("%d\n", ans);
	}
}