Problem Setter: Sagnik Chaudhuri

In order to achieve spiritual enlightenment and get free from the daily chores of his mundane life, Jadoo consulted a Saint who lived high atop a mountain. The Saint was willing to show the path to Jadoo only if Jadoo helped him solve a problem which has been bothering him for many years. The problem is :

"We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, a 4-digit Pandigital number which is also a prime is 2143. What is the largest n-digit pandigital prime which is <= M? If there is none, print -1"

Input Format

The first line contains T, the number of test cases. This is followed by T lines, each containing M.

Output Format

Print the required answer for each test case.

Constraints

1 <= T <= 100000,
10 <= M <= 10^10 - 1