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 c {

    static ArrayList<Integer> problem = new ArrayList<>();
    static PrintWriter out = new PrintWriter((System.out));
    static int maxInt = Integer.MAX_VALUE;
    static long maxLong = 100000000000L;
    static ArrayList<Integer>[] adj;
    static long[] pow, hash, inv;
    static int p = 31, mod = (int) 1e9 + 7;
    // static int n,p,k,x,y;
    static Reader sc = new Reader();

    public static void main(String args[]) throws IOException {

        ArrayList<Integer> primes = sieve(10000000);
        int t = sc.nextInt();
        while (t-- > 0)
            solve(primes);
        out.close();
    }

    // static long power(long a,long b){
    // long result=1;
    // while(b>0){
    // if(b%2!=0) result = (result * a) % mod;
    // a=(a*a)%mod;
    // b>>=1;
    // }
    // return result;
    // }
    // static void computePow(){
    // pow[0]=1;
    // for(int i=1;i<pow.length;i++){
    // pow[i]=(pow[i-1]*p)%mod;
    // }
    // }
    // static void computeHash(char[] s){
    // long ans=0;
    // for(int i=0;i<hash.length;i++){
    // ans=hash[i]=(ans+((s[i]-'a'+1)*pow[i])%mod)%mod;
    // }
    // }
    // static long findHash(char[] s){
    // long ans=0;
    // for(int i=0;i<s.length;i++){
    // ans=(ans+((s[i]-'a'+1)*pow[i])%mod)%mod;
    // }
    // return ans;
    // }
    // static void computeInv(){
    // inv[0]=1;
    // for(int i=1;i<inv.length;i++){
    // inv[i]=power(pow[i],mod-2);
    // }
    // }
    // static long substringHash(char[] s,int i,int j){
    // long ans=hash[j];
    // if(i>0){
    // ans=(ans-hash[i-1]+mod)%mod;
    // }
    // ans=(ans*inv[i])%mod;
    // return ans;
    // }
    public static void solve(ArrayList<Integer> primes) {
        int d = sc.nextInt();

        int first = -1, second = -1, prev = 1;
        for (int e : primes) {
            if (first != -1 && second != -1)
                break;
            if (first == -1) {
                if (e - prev >= d) {
                    first = e;
                    prev = e;
                }
            } else {
                if (e - prev >= d) {
                    second = e;
                    prev = e;
                }
            }
        }
        out.println(first * second);

    }

    static ArrayList<Integer> sieve(int n) {
        ArrayList<Integer> primes = new ArrayList<>();
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        for (int i = 2; i < n; i++) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    private static boolean noDivisor(int lim, long curr) {
        for (int k = 2; k <= lim; k++) {
            if (curr % k == 0)
                return false;
        }
        return true;
    }

    static class Reader {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                }
            return st.nextToken();
        }

        boolean hasNext() {
            return st.hasMoreTokens();
        }

        String nextLine() {
            String line = "";
            try {
                line = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}
