Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Ekupai

By SMAN2901 · Limits 1s, 32 MB

Hacker robot Ekupai is trying to hack a supercomputer. He needs a cheat code X to hack this computer where X is a non-negative integer. He doesn’t know how to find X. But he somehow managed to find an integer N, and he believes that N is equal to 6X. Unfortunately some (possibly zero) digits of N are missing.

Ekupai now wants to find the minimum possible value of N. But this task is too hard for him. So he asked for your help. If you refuse to help him, he will hack your computer and erase all of your important data.

Write a program for Ekupai that will find the minimum possible value of N that can be equal to 6X if it is possible.

Input

First line of the input will contain an integer T (1 ≤ T ≤ 100).

Each of the next T lines will contain a sequence of digits and asterisks (*) representing the integer N. Here asterisks represent missing digits. A sequence can contain zero or more asterisks characters.

Length of any sequence won’t be more than 100 and it won't contain any space or leading zeros.

Output

For each of T given sequences print the minimum possible value of N in a single line. Output shouldn't contain any leading zeros. If it is impossible to find a valid N, print "-1".

Sample

InputOutput
8
456*
45**
6
15
123******
*****123
*****124
*48

4560
4500
6
-1
123000000
-1
10001124
348

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.