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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.NoSuchElementException;
import java.util.Queue;

public class Main {
	private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	private BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	private StringTokenizer st;
	private Long MOD = 1000000007L;
	private final String endl = "\n";

	public static void main(String[] args) throws Exception {
		new Main().solve();
	}

	private void solve() throws Exception {

		int testCases = 1;
		testCases = Integer.parseInt(in.readLine().trim());
		preProcess();
		for (int i = 1; i <= testCases; i++) {
			solveTestCase(i);
		}

		out.flush();
		out.close();
	}

	void preProcess() {
		
		
		
		
	}
	
	boolean primes[] = sieveOfEratosthenes(100000);

	private void solveTestCase(int testCaseNumber) throws Exception {
			
		int d = ri();
		
		int i = 1 + d;
		
		long first = -1;
		
		for (;i < 100000; i++) {
			if (primes[i]) {
				first = i;
				break;
			}
		}
		
		long second = first  + d;
		
		i = (int)second;
		for (; i < 100000; i++) {
			if (primes[i]) {
				second = i;
				break;
			}
		}
		
		
		out.write(first * second + "\n");
	}

	
	boolean[] sieveOfEratosthenes(int n) 
    { 
        // Create a boolean array "prime[0..n]" and initialize 
        // all entries it as true. A value in prime[i] will 
        // finally be false if i is Not a prime, else true. 
        boolean prime[] = new boolean[n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) 
        { 
            // If prime[p] is not changed, then it is a prime 
            if(prime[p] == true) 
            { 
                // Update all multiples of p 
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
          
        return prime;
    } 
	
	// utils
	public long modInv(long a, long MOD) {
		return new BigInteger(a + "").modPow(new BigInteger((MOD - 2) + ""), new BigInteger(MOD + "")).longValue();
	}

	public long modPro(long a, long b, long MOD) {
		return ((a % MOD) * (b % MOD)) % MOD;
	}

	private long factorialMod(int n, long MOD) {
		long pro = 1;

		for (long i = 1; i <= n; i++) {
			pro = pro * i;
			pro %= MOD;
		}

		return pro;
	}

	// utilities below

	// IO UTILS

	void log(Object... args) {
		boolean testing = true;
		testing = false;

		if (!testing)
			return;

		for (Object s : args) {
			System.out.print(s.toString() + " ");
		}
		System.out.println();
	}

	String line() throws IOException {
		return in.readLine().trim();
	}

	StringTokenizer tokens() throws IOException {
		return new StringTokenizer(line());
	}

	long l(String s) {
		return Long.parseLong(s);
	}

	long rl() throws IOException {
		return l(line());
	}

	long[] rla(int n) throws IOException {
		long[] arr = new long[n];
		st = tokens();

		for (int i = 0; i < n; i++)
			arr[i] = l(st.nextToken());

		return arr;
	}

	int i(String s) {
		return Integer.parseInt(s);
	}

	int ri() throws IOException {
		return i(line());
	}

	int[] ria(int n) throws IOException {
		int[] arr = new int[n];
		st = tokens();

		for (int i = 0; i < n; i++)
			arr[i] = i(st.nextToken());

		return arr;
	}

	String rs() throws IOException {
		return line();
	}

	String[] rsa(int n) throws IOException {
		String s[] = new String[n];

		st = tokens();

		for (int i = 0; i < n; i++)
			s[i] = st.nextToken();

		return s;
	}

	double d(String s) {
		return Double.parseDouble(s);
	}

	double rd() throws IOException {
		return d(line());
	}

	double[] rda(int n) throws IOException {
		double[] arr = new double[n];
		st = tokens();

		for (int i = 0; i < n; i++) {
			arr[i] = d(st.nextToken());
		}

		return arr;
	}
	// IO UTILS END

	// MATH UTILS

	long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	// MATH UTILS END
}
