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

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_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 best = max(
        { r0, r1, q0, q1, q2 },
        [](optional<snext> const& a, optional<snext> const& b) {
            if (!a && !b)
                return false;
            if (!a)
                return true;
            if (!b)
                return false;

            if (a->size() < b->size())
                return true;
            if (a->size() > b->size())
                return false;

            return a->to_string() < b->to_string();
        }
    );

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

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

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

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

    int t;
    cin >> t;

    while (t--)
        solve();
}