#include <iostream>
using namespace std;
string largerString(string a, string b) {
int idxa = 0;
int idxb = 0;
while (idxa<a.size() && a[idxa] == '0') {
idxa++;
}
while (idxb < b.size() && b[idxb] == '0') {
idxb++;
}
a.erase(0, idxa);
b.erase(0, idxb);
if (a.size() > b.size()) return a;
else if (b.size() > a.size()) return b;
else {
for (size_t i = 0; i < a.size(); i++)
{
if (a[i] > b[i]) return a;
if (b[i] > a[i]) return b;
}
}
return a;
}
bool validString(string s) {
for (size_t i = 0; i < s.size(); i++)
{
if (s[i] != '0') return true;
}
return false;
}
int main()
{
int a;
cin >> a;
for (size_t i = 0; i < a; i++)
{
string input;
cin >> input;
int inpSum = 0;
int oneLeft = 0;
int twoLeft = 0;
for (size_t j = 0; j < input.size(); j++)
{
inpSum += input[j] - '0';
if (input[j] % 3 == 1) oneLeft++;
else if (input[j] % 3 == 2) twoLeft++;
}
inpSum %= 3;
// 0
if (inpSum == 0) {
cout << input << "\n";
continue;
}
// 1
if (inpSum == 1) {
int changeVal1 = 0;
int changeVal2 = 0;
int changeVal3 = 0;
int lr1 = 100'001;
int lr2 = 100'001;
int lr3 = 100'001;
int lr1Index = -1;
int lr2Index = -1;
int lr3Index = -1;
if (oneLeft > 0) {
for (size_t j = 0; j < input.size(); j++)
{
int val = input[j] - '0';
if (val % 3 == 1) {
if (j == input.size()-1) {
if (changeVal1 < 0) {
lr1 = 1;
lr1Index = j;
changeVal1 = 0;
}
}
for (size_t k = j+1; k < input.size(); k++)
{
if (j>0 || input[k] != '0') {
int curlr = k - j;
int curCV = input[k] - input[j];
if (curlr == 1 && curCV > 0) {
changeVal1 = curCV;
lr1 = 1;
lr1Index = j;
j = input.size();
k = input.size();
}
else if (curlr < lr1) {
lr1 = curlr;
changeVal1 = curCV;
lr1Index = j;
}
else if (curlr == lr1 && curCV >= changeVal1) {
changeVal1 = curCV;
lr1Index = j;
}
break;
}
}
}
}
//cout << lr1Index << " " << changeVal1 << " " << lr1 << "\n";
}
//1.2
if (twoLeft > 1 && lr1>1) {
for (size_t j = 0; j < input.size(); j++)
{
int val = input[j] - '0';
if (val % 3 == 2) {
for (size_t k = j + 1; k < input.size(); k++)
{
if (j > 0 || input[k] != '0') {
int curlr = k - j;
int curCV = input[k] - input[j];
if (curlr == 1 && curCV > 0) {
if (lr2 != 1 || changeVal2 < 0) {
changeVal3 = changeVal2;
lr3 = lr2;
lr3Index = lr2Index;
changeVal2 = curCV;
lr2 = 1;
lr2Index = j;
}
else if (lr3 != 1 || changeVal3 < 0) {
changeVal3 = curCV;
lr3 = 1;
lr3Index = j;
}
}
else if (curlr < lr2) {
changeVal3 = changeVal2;
lr3 = lr2;
lr3Index = lr2Index;
changeVal2 = curCV;
lr2 = curlr;
lr2Index = j;
}
else if (curlr < lr3) {
changeVal3 = curCV;
lr3 = curlr;
lr3Index = j;
}
else if (curlr == lr2 && curCV >= changeVal2) {
changeVal3 = changeVal2;
lr3 = lr2;
lr3Index = lr2Index;
changeVal2 = curCV;
lr2 = curlr;
lr2Index = j;
}
else if (curlr == lr3 && curCV >= changeVal3) {
changeVal3 = curCV;
lr3 = curlr;
lr3Index = j;
}
break;
}
}
}
}
//cout << lr2Index << " " << changeVal2 << " " << lr2 << "\n";
//cout << lr3Index << " " << changeVal3 << " " << lr3 << "\n";
}
//compare!
string oldInput = input;
if (lr1 != 100'001) {
input.erase(lr1Index, lr1);
}
string res1 = input;
input = oldInput;
if (lr3 != 100'001) {
input.erase(lr3Index, lr3);
}
if (lr2 != 100'001) {
input.erase(lr2Index, lr2);
}
string res2 = input;
input = oldInput;
if (res1 == oldInput) {
res1 = "0";
}
if (res2 == oldInput) {
res2 = "0";
}
string sol = largerString(res1, res2);
if (validString(sol)) cout << sol << "\n";
else cout << "-1\n";
}
// 2
if (inpSum == 2) {
int changeVal1 = 0;
int changeVal2 = 0;
int changeVal3 = 0;
int lr1 = 100'001;
int lr2 = 100'001;
int lr3 = 100'001;
int lr1Index = -1;
int lr2Index = -1;
int lr3Index = -1;
if (twoLeft > 0) {
for (size_t j = 0; j < input.size(); j++)
{
int val = input[j] - '0';
if (val % 3 == 2) {
if (j == input.size() - 1) {
if (changeVal1 < 0) {
lr1 = 1;
lr1Index = j;
changeVal1 = 0;
}
}
for (size_t k = j + 1; k < input.size(); k++)
{
if (j > 0 || input[k] != '0') {
int curlr = k - j;
int curCV = input[k] - input[j];
if (curlr == 1 && curCV > 0) {
changeVal1 = curCV;
lr1 = 1;
lr1Index = j;
j = input.size();
k = input.size();
}
else if (curlr < lr1) {
lr1 = curlr;
changeVal1 = curCV;
lr1Index = j;
}
else if (curlr == lr1 && curCV >= changeVal1) {
changeVal1 = curCV;
lr1Index = j;
}
break;
}
}
}
}
//cout << lr1Index << " " << changeVal1 << " " << lr1 << "\n";
}
//2.2
if (oneLeft > 1 && lr1 > 1) {
for (size_t j = 0; j < input.size(); j++)
{
int val = input[j] - '0';
if (val % 3 == 1) {
for (size_t k = j + 1; k < input.size(); k++)
{
if (j > 0 || input[k] != '0') {
int curlr = k - j;
int curCV = input[k] - input[j];
if (curlr == 1 && curCV > 0) {
if (lr2 != 1 || changeVal2 < 0) {
changeVal3 = changeVal2;
lr3 = lr2;
lr3Index = lr2Index;
changeVal2 = curCV;
lr2 = 1;
lr2Index = j;
}
else if (lr3 != 1 || changeVal3 < 0) {
changeVal3 = curCV;
lr3 = 1;
lr3Index = j;
}
}
else if (curlr < lr2) {
changeVal3 = changeVal2;
lr3 = lr2;
lr3Index = lr2Index;
changeVal2 = curCV;
lr2 = curlr;
lr2Index = j;
}
else if (curlr < lr3) {
changeVal3 = curCV;
lr3 = curlr;
lr3Index = j;
}
else if (curlr == lr2 && curCV >= changeVal2) {
changeVal3 = changeVal2;
lr3 = lr2;
lr3Index = lr2Index;
changeVal2 = curCV;
lr2 = curlr;
lr2Index = j;
}
else if (curlr == lr3 && curCV >= changeVal3) {
changeVal3 = curCV;
lr3 = curlr;
lr3Index = j;
}
break;
}
}
}
}
//cout << lr2Index << " " << changeVal2 << " " << lr2 << "\n";
//cout << lr3Index << " " << changeVal3 << " " << lr3 << "\n";
}
//compare!
string oldInput = input;
if (lr1 != 100'001) {
input.erase(lr1Index, lr1);
}
string res1 = input;
input = oldInput;
if (lr3 != 100'001) {
input.erase(lr3Index, lr3);
}
if (lr2 != 100'001) {
input.erase(lr2Index, lr2);
}
string res2 = input;
input = oldInput;
if (res1 != oldInput) {
cout << res1 << " ";
}
if (res2 != oldInput) {
cout << res2;
}
cout << "\n";
}
}
}