#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 5e5 + 3;
const int INF = 1e9;

int dp[N][3][2];

void input(string s){
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    input("three");

    int t;
    cin >> t;

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

        int n = s.size();
        bool can_zero = false;
        for(int i = 0; i < n; ++i)
            if(s[i] == '0'){
                can_zero = true;
                break;
            }

        dp[n][0][0] = 0;
        dp[n][0][1] = 0;
        dp[n][1][0] = -INF;
        dp[n][1][1] = -INF;
        dp[n][2][0] = -INF;
        dp[n][2][1] = -INF; 
        for(int i = n - 1; i >= 0; --i)
            for(int j = 0; j < 3; ++j){
                for(int k = 0; k < 2; ++k){
                    dp[i][j][k] = -INF;
                    if(s[i] != '0') dp[i][j][k] = max(dp[i + 1][(j + s[i] - '0') % 3][true] + 1, dp[i][j][k]);
                    else if(k) dp[i][j][k] = max(dp[i + 1][(j + s[i] - '0') % 3][true] + 1, dp[i][j][k]);
                    dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
                }
            }

        if(dp[0][0][0] == 0){
            if(can_zero) cout << "0\n";
            else cout << "-1\n";
            continue;
        }

        int i = 0, j = 0, k = 0;
        while(i != n){
            if(dp[i + 1][j][k] > dp[i + 1][(j + s[i] - '0') % 3][k] + 1 || (!k && s[i] == '0')){
                ++i;
            }
            else{
                cout << s[i];
                j = (j + s[i] - '0') % 3;
                ++i;
                k = true;
            }
        }
        cout << "\n";
    }
}