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.

/**
* Date: 
* Link:
*
* @author: Prasad Chaudhari
* @linkedIn: https://www.linkedin.com/in/prasad-chaudhari-841655a6/
* @git: https://github.com/Prasad-Chaudhari
*/
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws Exception {
        FastIO in = new FastIO(args);
        int t = in.ni();
        Primes p = new Primes(1000000);
        int primes[] = p.primes();
        while (t-- > 0) {
            int d = in.ni();
            int index = Arrays.binarySearch(primes, d + 1);
            int p1 = -1;
            if (index >= 0) {
                p1 = primes[index];
            } else {
                index = -index - 1;
                p1 = primes[index];
            }
            int p2 = -1;
            index = Arrays.binarySearch(primes, d + p1);
            if (index >= 0) {
                p2 = primes[index];
            } else {
                index = -index - 1;
                p2 = primes[index];
            }
            // System.out.println(p1 + " " + p2);
            System.out.println(1l * p1 * p2);
        }
        in.bw.flush();
    }

    static public class Primes {

        private int smallest_primes[];
        private int primes[];

        public Primes(int n) {
            boolean[] c = new boolean[n + 1];
            int nop = 0;
            int root = (int) (Math.sqrt(n) + 1);
            smallest_primes = new int[n + 1];
            for (int i = 2; i <= n; i++) {
                smallest_primes[i] = i;
            }
            for (int i = 2; i <= root; i++) {
                if (!c[i]) {
                    smallest_primes[i] = i;
                    for (int j = i * i; j <= n; j = j + i) {
                        if (!c[j])
                            smallest_primes[j] = i;
                        c[j] = true;
                    }
                }
            }
            for (int i = 2; i <= n; i++) {
                nop += !c[i] ? 1 : 0;
            }
            primes = new int[nop];
            nop = 0;
            for (int i = 2; i <= n; i++) {
                if (!c[i]) {
                    primes[nop++] = i;
                }
            }
        }

        public int[] primes() {
            return Arrays.copyOf(primes, primes.length);
        }

        public int[] smallest_primes() {
            return Arrays.copyOf(smallest_primes, smallest_primes.length);
        }
    }

    static class Data implements Comparable<Data> {

        int a, b, c;

        public Data(int a, int b, int c) {
            this.a = a;
            this.c = c;
            this.b = b;
        }

        @Override
        public int compareTo(Data o) {
            if (a == o.a) {
                return Integer.compare(b, o.b);
            }
            return Integer.compare(a, o.a);
        }

        // public static void sort(int a[]) {
        // Data d[] = new Data[a.length];
        // for (int i = 0; i < a.length; i++) {
        // d[i] = new Data(a[i], 0);
        // }
        // Arrays.sort(d);
        // for (int i = 0; i < a.length; i++) {
        // a[i] = d[i].a;
        // }
        // }
    }

    static class FastIO {

        private final BufferedReader br;
        private final BufferedWriter bw;
        private String s[];
        private int index;

        public FastIO(String[] args) throws IOException {
            if (args.length > 1) {
                br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(args[0]))));
                bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(new File(args[1]))));
            } else {
                br = new BufferedReader(new InputStreamReader(System.in));
                bw = new BufferedWriter(new OutputStreamWriter(System.out, "UTF-8"));
            }
            s = br.readLine().split(" ");
            index = 0;
        }

        public int ni() throws IOException {
            return Integer.parseInt(nextToken());
        }

        public double nd() throws IOException {
            return Double.parseDouble(nextToken());
        }

        public long nl() throws IOException {
            return Long.parseLong(nextToken());
        }

        public String next() throws IOException {
            return nextToken();
        }

        public String nli() throws IOException {
            try {
                return br.readLine();
            } catch (IOException ex) {

            }
            return null;
        }

        public int[] gia(int n) throws IOException {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public int[] gia(int n, int start, int end) throws IOException {
            validate(n, start, end);
            int a[] = new int[n];
            for (int i = start; i < end; i++) {
                a[i] = ni();
            }
            return a;
        }

        public double[] gda(int n) throws IOException {
            double a[] = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }

        public double[] gda(int n, int start, int end) throws IOException {
            validate(n, start, end);
            double a[] = new double[n];
            for (int i = start; i < end; i++) {
                a[i] = nd();
            }
            return a;
        }

        public long[] gla(int n) throws IOException {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }

        public long[] gla(int n, int start, int end) throws IOException {
            validate(n, start, end);
            long a[] = new long[n];
            for (int i = start; i < end; i++) {
                a[i] = nl();
            }
            return a;
        }

        public void print(String s) throws IOException {
            bw.write(s);
        }

        public void println(String s) throws IOException {
            bw.write(s);
            bw.newLine();
        }

        public void print(int s) throws IOException {
            bw.write(s + "");
        }

        public void println(int s) throws IOException {
            bw.write(s + "");
            bw.newLine();
        }

        public void print(long s) throws IOException {
            bw.write(s + "");
        }

        public void println(long s) throws IOException {
            bw.write(s + "");
            bw.newLine();
        }

        public void print(double s) throws IOException {
            bw.write(s + "");
        }

        public void println(double s) throws IOException {
            bw.write(s + "");
            bw.newLine();
        }

        private String nextToken() throws IndexOutOfBoundsException, IOException {
            if (index == s.length) {
                s = br.readLine().split(" ");
                index = 0;
            }
            return s[index++];
        }

        private void validate(int n, int start, int end) {
            if (start < 0 || end >= n) {
                throw new IllegalArgumentException();
            }
        }
    }
}
