import java.io.*;
import java.util.*;
import java.util.stream.*;
import java.lang.*;
import java.io.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
          List<Integer> pandigitals = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            List<String> digits = IntStream.rangeClosed(1, i)
                    .mapToObj(Integer::toString)
                    .collect(Collectors.toList());
            List<List<String>> permutations = getPermutations(digits);
            for (List<String> p : permutations) {
                int num = Integer.parseInt(String.join("", p));
                if (isPrime(num)) {
                    pandigitals.add(num);
                }
            }
        }
        pandigitals.sort(Comparator.naturalOrder());

        try {
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(reader.readLine());
            for (int t = 0; t < n; t++) {
                int query = Integer.parseInt(reader.readLine());
                int answer = pandigitals.stream()
                        .filter(p -> p <= query)
                        .reduce((first, second) -> second)
                        .orElse(-1);
                System.out.println(answer != 0 ? Integer.toString(answer) : "-1");
            }
        } catch (IOException ex) {
            System.out.println("Error: " + ex.getMessage());
        }
    }

    static boolean 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 List<List<String>> getPermutations(List<String> list) {
        if (list.size() == 1) {
            List<List<String>> result = new ArrayList<>();
            result.add(list);
            return result;
        }

        List<List<String>> permutations = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            String a = list.get(i);
            List<String> remaining = new ArrayList<>(list.subList(0, i));
            remaining.addAll(list.subList(i + 1, list.size()));
            List<List<String>> subPermutations = getPermutations(remaining);
            for (List<String> subPerm : subPermutations) {
                List<String> permutation = new ArrayList<>();
                permutation.add(a);
                permutation.addAll(subPerm);
                permutations.add(permutation);
            }
        }
        return permutations;
    }
}