Orlando is preparing for the aptitude round and for this he has taken a course on HIREDIVE. Rosalind (Orlando’s crush) has also enrolled for the same course. On the occasion of Hug Day, Orlando called up Rosalind at his place for group study. While solving previous year questions, Orlando tried to hug Rosalind but she stopped him and gave him a piece of puzzle to solve. She agreed to celebrate Hug Day with him only if he solves the puzzle within the given time. Since Orlando does not know any programming language, he has asked for your help!

Given a number M with N digits (where 1 ≤ N ≤ 100000), Rosalind wants to know the largest permutation of the N digits for which M mod 6 = 3 where mod represents the modulo operation. Print -1 if it’s impossible to find such a permutation.

Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains a number M.

Output:

For each test case, print a single line containing the largest permutation of digits of the given number N such that N%6 = 3.
Print -1 if it’s impossible to find such a permutation.

Constraints:

1 ≤ T ≤ 10
1 ≤ N ≤ 100000, where N is the number of digits in the number.