using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    static bool IsPrime(int n) {
        if (n == 1 || (n % 2 == 0 && n != 2))
            return false;
        for (int i = 3; i <= Math.Sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    static void Main(string[] args) {
        List<int> pandigitals = new List<int>();
        for (int i = 1; i < 10; i++) {
            var permutations = GetPermutations(Enumerable.Range(1, i).Select(n => n.ToString()).ToArray());
            foreach (var p in permutations) {
                int num = int.Parse(string.Join("", p));
                if (IsPrime(num))
                    pandigitals.Add(num);
            }
        }
        pandigitals.Sort();

        try {
            int n = int.Parse(Console.ReadLine());
            for (int t = 0; t < n; t++) {
                int query = int.Parse(Console.ReadLine());
                int answer = pandigitals.LastOrDefault(p => p <= query);
                Console.WriteLine(answer != 0 ? answer.ToString() : "-1");
            }
        } catch (Exception ex) {
            Console.WriteLine("Error: " + ex.Message);
        }
    }

    static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list) {
        if (list.Count() == 1)
            return new List<IEnumerable<T>> { list };

        return list.SelectMany((a, i1) => GetPermutations(list.Where((b, i2) => i2 != i1)).Select(b => (new T[] { a }).Concat(b)));
    }
}