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
| Input | Output |
|---|---|
8 456* 45** 6 15 123****** *****123 *****124 *48 | 4560 4500 6 -1 123000000 -1 10001124 348 |
