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.util.*;

import java.io.*;

public class cp {

	static int gcd(int a, int b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
     
    // method to return LCM of two numbers
    static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }
	public static void main(String[] args) {
		ArrayList<Integer> lt = primes(100000);
		FastReader sc = new FastReader();
		int t = sc.nextInt();
		while(t-- != 0) {
			int d = sc.nextInt();
			int ans = 1;
			ans *= search(lt, ans + d);
			ans *= search(lt, ans + d);
			System.out.println(ans);
		}
	}

	static int search(ArrayList<Integer> lt, int a) {
		if(a == 1)return 2;
		return search(lt, a, 0, lt.size() - 1);
	}
	static int search(ArrayList<Integer> lt, int a, int start, int end) { // returning the forward value
		int n = lt.size();
		if(start < 0 || end >= n)return -1;
		if(start == end) {
			if(lt.get(end) < a) {
				if(end < n - 1 && lt.get(end + 1) >= a) return lt.get(end + 1);
				else return -1;
			}else if(lt.get(end) == a)return a;
			else if(end > 0 && lt.get(end - 1) < lt.get(end))return lt.get(end);
			else return -1;
		}
		int mid = (start + end) / 2;
//		System.out.println(lt.get(start) + " " + lt.get(mid) + " " + lt.get(end));
		if(lt.get(mid) == a)return a;
		if(lt.get(mid) > a)return search(lt, a, start, mid);
		else return search(lt, a, mid + 1, end);
	}
	static long solve(boolean[] visited, int k, int s, int e, HashMap<Integer, Set<Integer>> mapL, HashMap<Integer, Set<Integer>> mapIl) {
		
		if(visited[s])return -1;
		visited[s] = true;
		if(mapL.containsKey(s) && mapL.get(s).contains(e))return 0;
		if(mapIl.containsKey(s) && mapIl.get(s).contains(e))return k;
		long min = Long.MAX_VALUE;
		if(mapL.containsKey(s)) {
			Set<Integer> set = mapL.get(s);
			for(int d : set) {
				long dis = solve(visited, k, d, e, mapL, mapIl);
				if(dis != -1)return dis;
			}
		}
		if(mapIl.containsKey(s)) {
			Set<Integer> set = mapIl.get(s);
			for(int d : set) {
				long dis = solve(visited, k, d, e, mapL, mapIl);
				if(dis != -1)return dis + k;
			}
		}
		
		return -1;
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

	public static ArrayList<Integer> primes(int a){
		ArrayList<Integer> lt = new ArrayList<Integer>();
		boolean[] isPrime = new boolean[a + 2];
		Arrays.fill(isPrime, true);
				
		int n = a + 1;
		int i = 2;
		for(; i * i <= n; i++) {
			if(isPrime[i]) {
				lt.add(i);
				for(int j = i * i; j <= n; j += i) {
					isPrime[j] = false;
				}
			}
		}
		for(; i <= a; i++)if(isPrime[i])lt.add(i);
		return lt;
	}
static class SegmentTree {
	long[] arr;
	int size;
	public SegmentTree(int[] input) { // l and r are the index of array 'input' (zero based indexing)
		arr = new long[(input.length) * 4];
		size = input.length;
		formTree(0, input.length - 1, 1, input);
	}
	public void formTree(int l, int r, int i, int[] input) {
		if(r == l) {
			arr[i] = input[r];
			return;
		}
		int mid = (l + r) / 2;
		formTree(l, mid, 2 * i, input);
		formTree(mid + 1, r, 2 * i + 1, input);
		arr[i] = arr[2 * i] + arr[2 * i + 1]; 
	}
	
	public void print() {
		System.out.print(" ");
		for(long e : arr) {
			
			if(e == 0)System.out.print("_");
			while(e != 0) {
				System.out.print("_");
				e /= 10;
			}
			System.out.print(" ");
			
		}
		System.out.println();
		System.out.print("|");
		for(long e : arr)System.out.print(e + "|");
		System.out.println();
	}
	
	public long get(int l, int r) { // inclusively
		return get(l, r, 0, size - 1, 1);
	}
	public long get(int l, int r, int start, int end, int treeIn) {
//		System.out.println(start + " " + l + " " + r + " " + end +" " + treeIn);
		if(start < 0 || end >= size || (start > r) || end < l)return 0;
		if(start >= l && end <= r) return arr[treeIn];
		int mid = (start + end) / 2;
		return (long)get(l, r, start, mid, 2 * treeIn) + (long)get(l, r, mid + 1, end, 2 * treeIn + 1);
		
	}
	public void update(int i, long val) {
		update( i, 0, size - 1, 1, val);
	}
	
	public long update(int i, int start, int end, int treeIn, long val) {

		if(start < 0 || end >= size)return 0;
		
		if(start == end && end == i) {
			long sum = arr[treeIn];
			arr[treeIn] = val;
			return sum - val;
		}
		int mid = (start + end) / 2;
		
		if(mid >= i) {
			long sum = update(i, start, mid, 2 * treeIn, val);
			arr[treeIn] -= sum;
			return sum;
		}
		if(mid < i) {
			long sum = update(i, mid + 1, end, 2 * treeIn + 1, val);
			arr[treeIn] -= sum;
			return sum;
		}
		return 0;
	}
}
}	

