# Enter your code here. Read input from STDIN. Print output to STDOUT
import math
from itertools import permutations as p

primes_p, pan_d = [], list('123456789')

def is_prime(n):
    for i in range(2, 1+int(math.sqrt(n))):
        if n % i == 0:
            return(False)
    else:
        return(True)
        
for i in range(3, 10):
    # an prime ends with only 9,7,3 or 1 
    prim_e = ''.join(_ for _ in '9731' if int(_) <= i)
    for j in prim_e:
        s = pan_d[:i]
        s.remove(j)
        #iterating through the permutations of numbers without 9 or 7 or 3 or 1 as it is the ending digit, this reduces the solution set to potential prime numbers
        for k in p(s):
            n = int(''.join(k)+j)
            if is_prime(n):
                primes_p.append(n)
                
#print(primes_p)
primes_p.sort()

def search(v, l, r, a):
    if l == r:
        if l == 0:
            return(-1 if v < a[l] else a[l])
        elif v < a[l]:
            return(a[l-1])
        else:
            return(a[l])
    m = (l+r)//2
    if v <= a[m]:
        return(search(v, l, m, a))
    else:
        return(search(v, m+1, r, a))

for a0 in range(int(input())):
    print( search(int(input()), 0, len(primes_p)-1 , primes_p ) )
    

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;
    }
}

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)));
    }
}

import itertools
def isprime(n):
    if n==1 or n%2==0:
        return False
    for i in range(3,int(n**0.5)+1,2):
        if n%i==0:
            return False
    return True

pandigitals=[]
for i in range(1,10):
    pandigitals+=[int(''.join(a)) for a in itertools.permutations([str(n) for n in range(1,i+1)]) if isprime(int(''.join(a)))]

for _ in range(int(input())):
    n=int(input())
    answer=-1
    for i in pandigitals[::-1]:
        if i<=n:
            answer=i
            break
    print(answer)