#include <algorithm>
#include <iostream>
#include <optional>
#include <vector>

#ifndef ONLINE_JUDGE
#include <string>
#endif

using namespace std;

struct snext {
    vector<int> s;
    vector<int> next;
    vector<bool> deleted;

    int size() const {
        return s.size();
    }

    snext(string const& x) : s(x.size()), next(x.size()), deleted(x.size(), false) {
        for (int i = 0; i < size(); i++)
            s[i] = x[i] - '0';

        next.back() = 0;
        for (int i = size() - 2; i >= 0; i--) {
            if (s[i] != s[i + 1])
                next[i] = s[i + 1];
            else
                next[i] = next[i + 1];
        }
    }

    int rem() const {
        int ret = 0;

        for (int i = 0; i < size(); i++)
            if (!deleted[i])
                ret = (ret + s[i]) % 3;

        return ret;
    }

    string to_string() const {
        string ret;

        for (int i = 0; i < size(); i++)
            if (!deleted[i])
                ret.push_back(s[i] + '0');

        return ret;
    }
};

optional<snext> remove_backward(snext num, int const mod, int cnt, int const start) {
    for (int i = num.s.size() - 1; i >= start; i--) {
        if (!num.deleted[i] && num.s[i] % 3 == mod) {
            num.deleted[i] = true;
            cnt--;

            if (cnt == 0)
                return num;
        }
    }

    return nullopt;
}

optional<snext> remove_forward(snext num, int const mod, int cnt, int const start) {
    for (int i = start; i < num.s.size(); i++) {
        if (!num.deleted[i] && num.s[i] % 3 == mod && num.next[i] > num.s[i]) {
            num.deleted[i] = true;
            cnt--;

            if (cnt == 0)
                return num;
        }
    }

    return remove_backward(num, mod, cnt, start);
}

optional<snext> remove_forward_double(snext num, int const mod, int const start) {
    for (int i = start; i < num.s.size() - 1; i++) {
        if (
            !num.deleted[i]
            && num.s[i] % 3 == mod && num.s[i + 1] % 3 == mod
            && (i == num.size() - 2 || num.s[i + 2] > num.s[i])
        ) {
            num.deleted[i] = true;
            num.deleted[i + 1] = true;
            
            return num;
        }
    }

    return nullopt;
}

optional<snext> remove_beginning(snext num, int const mod, int cnt_total, int cnt_beginning) {
    int start = 0;

    while (true) {
        if (cnt_beginning == 0)
            break;

        if (num.s[start] % 3 != mod)
            return nullopt;

        num.deleted[start] = true;
        start++;

        while (start < num.s.size() && num.s[start] == 0) {
            num.deleted[start] = true;
            start++;
        }

        if (start == num.size())
            return nullopt;

        cnt_total--;
        cnt_beginning--;
    }

    if (cnt_total == 0)
        return num;

    start++;
    if (start == num.size())
        return nullopt;

    return remove_forward(num, mod, cnt_total, start);
}

string solve(string const& x) {
    snext const s = x;

    int const r = s.rem();
    int const q = 3 - r;

    if (r == 0)
        return x;

    optional<snext> const r0 = remove_beginning(s, r, 1, 0);
    optional<snext> const r1 = remove_beginning(s, r, 1, 1);

    optional<snext> const q0 = remove_beginning(s, q, 2, 0);
    optional<snext> const q1 = remove_beginning(s, q, 2, 1);
    optional<snext> const q2 = remove_beginning(s, q, 2, 2);

    optional<snext> const qd = remove_forward_double(s, q, 1);

    optional<snext> const best = max(
        { r0, r1, q0, q1, q2, qd },
        [](optional<snext> const& a, optional<snext> const& b) {
            if (!a && !b)
                return false;
            if (!a)
                return true;
            if (!b)
                return false;

            string as = a->to_string();
            string bs = b->to_string();

            if (as.size() < bs.size())
                return true;
            if (as.size() > bs.size())
                return false;

            return as < bs;
        }
    );

    if (best) {
        string const ret = best->to_string();
        return ret;
    }
    else
        return "-1";
}

void solve() {
    string s;
    cin >> s;

    cout << solve(s) << "\n";
}

#ifndef ONLINE_JUDGE
using ll = long long;

bool div3(string const s) {
    int rem = 0;

    for (char const& c : s)
        rem = (rem + (c - '0')) % 3;

    return rem == 0;
}

string brute_solve(string const s) {
    string best = "";

    for (int mask = 1; mask < (1 << s.size()); mask++) {
        string cur;

        for (int i = 0; i < s.size(); i++)
            if ((mask >> i) & 1)
                cur.push_back(s[i]);

        if (cur[0] == '0')
            continue;

        if (!div3(cur))
            continue;

        if (cur.size() > best.size() || (cur.size() == best.size() && cur > best))
            best = cur;
    }

    if (best == "")
        return "-1";
    else
        return best;
}

void test(ll const n) {
    string const s = to_string(n);

    string const output = solve(s);
    string const answer = brute_solve(s);

    if (output != answer) {
        cout << "input = " << s << "; output = " << output << "; answer = " << answer << "\n";
        exit(0);
    }
}

void test() {
    for (ll i = 1; i < 1'000'000'000; i++) {
        test(i);

        if ((i >> 14 << 14) == i) {
            cout << "done: " << i << endl;
        }
    }
}
#endif

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

#ifndef ONLINE_JUDGE
    if (t == -1) {
        test();
        return 0;
    }
#endif

    while (t--)
        solve();
}