def getNum(digit):
return ord(digit) - ord('0')
def divisible(n):
if ord(n[-1]) % 2 != 0:
return False
digit_sum = sum([getNum(i) for i in n])
return digit_sum % 3 == 0
def getRes(n, mod):
d = []
leftMost = -1
rightMost = -1
for index, digit in enumerate(n):
# if current digit can be deleted
if getNum(digit) % 3 == mod:
# if the next digit is greater or equal than current
if index != len(n) - 1 and getNum(n[index + 1]) >= getNum(digit):
leftMost = index
break
if index == len(n) - 1:
if divisible(n[:-1]):
rightMost = index
else:
rightMost = index
target = 0
if leftMost != -1:
target = leftMost
elif rightMost != -1:
target = rightMost
else:
return -1
res = n[:target] + n[target + 1:]
return res
for _ in range(int(input())):
n = input()
if divisible(n):
print(getRes(n, 0))
continue
# if last digit is not even
if getNum(n[-1]) % 2 != 0:
# if 0 to n - 1 is divisible by 6
if divisible(n[:-1]):
print(n[:-1])
else:
print(-1)
else:
sum_digits = sum([getNum(i) for i in n])
mod = sum_digits % 3
print(getRes(n, mod))
ZGVmIGdldE51bShkaWdpdCk6CiAgICByZXR1cm4gb3JkKGRpZ2l0KSAtIG9yZCgnMCcpCgoKZGVmIGRpdmlzaWJsZShuKToKICAgIGlmIG9yZChuWy0xXSkgJSAyICE9IDA6CiAgICAgICAgcmV0dXJuIEZhbHNlCgogICAgZGlnaXRfc3VtID0gc3VtKFtnZXROdW0oaSkgZm9yIGkgaW4gbl0pCgogICAgcmV0dXJuIGRpZ2l0X3N1bSAlIDMgPT0gMAoKCmRlZiBnZXRSZXMobiwgbW9kKToKICAgIGQgPSBbXQoKICAgIGxlZnRNb3N0ID0gLTEKICAgIHJpZ2h0TW9zdCA9IC0xCiAgICBmb3IgaW5kZXgsIGRpZ2l0IGluIGVudW1lcmF0ZShuKToKICAgICAgICAjIGlmIGN1cnJlbnQgZGlnaXQgY2FuIGJlIGRlbGV0ZWQKICAgICAgICBpZiBnZXROdW0oZGlnaXQpICUgMyA9PSBtb2Q6CgogICAgICAgICAgICAjIGlmIHRoZSBuZXh0IGRpZ2l0IGlzIGdyZWF0ZXIgb3IgZXF1YWwgdGhhbiBjdXJyZW50CiAgICAgICAgICAgIGlmIGluZGV4ICE9IGxlbihuKSAtIDEgYW5kIGdldE51bShuW2luZGV4ICsgMV0pID49IGdldE51bShkaWdpdCk6CiAgICAgICAgICAgICAgICBsZWZ0TW9zdCA9IGluZGV4CiAgICAgICAgICAgICAgICBicmVhawoKICAgICAgICAgICAgaWYgaW5kZXggPT0gbGVuKG4pIC0gMToKICAgICAgICAgICAgICAgIGlmIGRpdmlzaWJsZShuWzotMV0pOgogICAgICAgICAgICAgICAgICAgIHJpZ2h0TW9zdCA9IGluZGV4CiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByaWdodE1vc3QgPSBpbmRleAogICAgdGFyZ2V0ID0gMAogICAgaWYgbGVmdE1vc3QgIT0gLTE6CiAgICAgICAgdGFyZ2V0ID0gbGVmdE1vc3QKICAgIGVsaWYgcmlnaHRNb3N0ICE9IC0xOgogICAgICAgIHRhcmdldCA9IHJpZ2h0TW9zdAogICAgZWxzZToKICAgICAgICByZXR1cm4gLTEKCiAgICByZXMgPSBuWzp0YXJnZXRdICsgblt0YXJnZXQgKyAxOl0KICAgIHJldHVybiByZXMKCgpmb3IgXyBpbiByYW5nZShpbnQoaW5wdXQoKSkpOgogICAgbiA9IGlucHV0KCkKCiAgICBpZiBkaXZpc2libGUobik6CiAgICAgICAgcHJpbnQoZ2V0UmVzKG4sIDApKQogICAgICAgIGNvbnRpbnVlCgogICAgIyBpZiBsYXN0IGRpZ2l0IGlzIG5vdCBldmVuCiAgICBpZiBnZXROdW0oblstMV0pICUgMiAhPSAwOgogICAgICAgICMgaWYgMCB0byBuIC0gMSBpcyBkaXZpc2libGUgYnkgNgogICAgICAgIGlmIGRpdmlzaWJsZShuWzotMV0pOgogICAgICAgICAgICBwcmludChuWzotMV0pCiAgICAgICAgZWxzZToKICAgICAgICAgICAgcHJpbnQoLTEpCiAgICBlbHNlOgogICAgICAgIHN1bV9kaWdpdHMgPSBzdW0oW2dldE51bShpKSBmb3IgaSBpbiBuXSkKICAgICAgICBtb2QgPSBzdW1fZGlnaXRzICUgMwogICAgICAgIHByaW50KGdldFJlcyhuLCBtb2QpKQo=