#include using namespace std; int t; char buf[100002]; vector > v; void reset(vector > &r){ vector > f; int pr = r[0].first; int cnt = 0; for (int i = 0; i < r.size(); i++){ if (pr == r[i].first){ cnt += r[i].second; } else{ f.push_back(make_pair(pr, cnt)); pr = r[i].first; cnt = r[i].second; } } f.push_back(make_pair(pr, cnt)); r = f; } int main(){ cin >> t; while (t--){ scanf("%s", buf); v.clear(); int siz = strlen(buf); for (int i = 0; i < siz; i++){ v.push_back(make_pair(buf[i] - '0', 1)); } reset(v); while (v.size()>1 || (v.size() == 1 && v[0].second>1)){ vector > tmp; int pr = -1; for (int i = 0; i < v.size(); i++){ if (v[i].second > 1){ int K = v[i].first + v[i].first; if (K >= 10){ K %= 10; K++; } tmp.push_back(make_pair(K, v[i].second - 1)); } if (i + 1 < v.size()){ int F = v[i].first + v[i + 1].first; if (F >= 10){ F %= 10; F++; } tmp.push_back(make_pair(F, 1)); } } v = tmp; reset(v); tmp.clear(); bool ng = false; int cnt = 0; for (int i = 0; i < v.size(); i++){ if (v[i].first == 3 || v[i].first == 6){ continue; } cnt++; } if (cnt<330)break; } printf("%d\n", v[0].first); } return 0; }