Positive integer x is called divisor of positive integer y, if y is divisible by x without remainder. For example, 1 is a divisor of 7 and 3 is not divisor of 8.

We gave you an integer d and asked you to find the smallest positive integer a, such that 

  * a has at least 4 divisors; 
  * difference between any two divisors of a is at least d.

Input

The first line contains a single integer t (1 ≤ t ≤ 3000) — the number of test cases.

The first line of each test case contains a single integer d (1 ≤ d ≤ 10000).

Output

For each test case print one integer a — the answer for this test case.

Example

Input


2
1
2


Output


6
15

Note

In the first test case, integer 6 have following divisors: [1, 2, 3, 6]. There are 4 of them and the difference between any two of them is at least 1. There is no smaller integer with at least 4 divisors.

In the second test case, integer 15 have following divisors: [1, 3, 5, 15]. There are 4 of them and the difference between any two of them is at least 2.

The answer 12 is INVALID because divisors are [1, 2, 3, 4, 6, 12]. And the difference between, for example, divisors 2 and 3 is less than d=2.
import java.io.*;
import java.util.*;

public class Main {
    public static int countDivisors(int n)
    {
        int cnt = 0;
        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0) {
                // If divisors are equal,
                // count only one
                if (n / i == i) {
                    pw.println(i);
                    cnt++;
                }

                else // Otherwise count both
                    cnt = cnt + 2;
            }
        }
        return cnt;
    }
    static boolean[] prime;
    public static void sieve(){
        int n = 30000;
        prime = new boolean[n+1];
        Arrays.fill(prime, true);

        for(int p = 2; p*p <=n; p++)
        {
            // If prime[p] is not changed, then it is a prime
            if(prime[p])
            {
                // Update all multiples of p
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }
    }

    public static long findFirstPrime(long start){
        for (long i = start; i < prime.length; i++) {
            if(prime[(int) i]) return i;
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        sieve();
        int tc = sc.nextInt();
        long ans = 0;
        while(tc-- > 0){
            long d = sc.nextLong();
            if(d == 1) pw.println(6);
            else if(d == 2) pw.println(15);
            else {
                    long x = findFirstPrime(d + 1);
                    ans = x * findFirstPrime(x + d);
                    pw.println(ans);
            }
        }
//        pw.println(countDivisors((int) ans));
        pw.close();
    }

    public static void pairSort(Pair[] arr) {
        ArrayList<Pair> l = new ArrayList<>();
        for (Pair i : arr) l.add(i);
        Collections.sort(l);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = l.get(i);
        }
    }
    public static void longSort(long[] arr) {
        ArrayList<Long> l = new ArrayList<>();
        for (long i : arr) l.add(i);
        Collections.sort(l);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = l.get(i);
        }
    }
    public static void intSort(int[] arr) {
        ArrayList<Integer> l = new ArrayList<>();
        for (int i : arr) l.add(i);
        Collections.sort(l);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = l.get(i);
        }
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

        public int[] nextIntArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(next());
            }
            return arr;
        }

        public long[] nextLongArr(int n) throws IOException {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Long.parseLong(next());
            }
            return arr;
        }

    }
    static class Pair implements Comparable<Pair>{
        int first, second;
        public Pair(int first, int second){
            this.first = first; this.second = second;
        }

        @Override
        public int compareTo(Pair p2) {
            return first - p2.first;
        }

        @Override
        public String toString() { return "("+ first + "," + second + ')'; }

    }

    static PrintWriter pw = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static final int MOD = (int) 1e9 + 7;
    static Random random = new Random();
}