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 C680 {
	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; 
        }
        int[] nextArray(int n)
        {
        	int arr[]=new int[n];
        	for(int i=0;i<n;i++)
        		arr[i]=nextInt();
        	return arr;
        }
    } 
	private static int V ; 
    private static List<List<Integer>> adj; 
    public C680(int V)  
    { 
        this.V = V; 
        adj = new ArrayList<>(V); 
          
        for (int i = 0; i < V; i++) 
            adj.add(new LinkedList<>()); 
    } 
	static void sum(int nums[],int i,ArrayList<Integer> a,ArrayList<Integer> b,HashSet<String> hSet)
	{
		if(i==nums.length)
		{
			Collections.sort(a);
			Collections.sort(b,Collections.reverseOrder());
			String string=a.toString()+b.toString();
			if(hSet.contains(string))
				return;
			else {
				
			}
		}
	}
	static long gcd(long a, long b)
    {
		//System.out.println(a+","+b);
        // Everything divides 0 
        if (a == 0)
          return b;
        if (b == 0)
          return a;
      
        // base case
        if (a == b)
            return a;
      
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
	static long findGCD(long arr[], int n) 
    { 
        long result = 0; 
        for (long element: arr){ 
            result = gcd(result, element); 
  
            if(result == 1) 
            { 
               return 1; 
            } 
        } 
  
        return result; 
    } 
		private static boolean isCyclicUtil(int i, boolean[] visited, 
			            boolean[] recStack)  
			{ 
			
			// Mark the current node as visited and 
			// part of recursion stack 
			if (recStack[i]) 
			return true; 
			
			if (visited[i]) 
			return false; 
			
			visited[i] = true; 
			
			recStack[i] = true; 
			List<Integer> children = adj.get(i); 
			
			for (Integer c: children) 
			if (isCyclicUtil(c, visited, recStack)) 
			return true; 
			
			recStack[i] = false; 
			
			return false; 
			} 
			
			
			
			// Returns true if the graph contains a  
			// cycle, else false. 
			// This function is a variation of DFS() in  
			// https://www.geeksforgeeks.org/archives/18212 
			private static boolean isCyclic()  
			{ 
			
			// Mark all the vertices as not visited and 
			// not part of recursion stack 
			boolean[] visited = new boolean[V]; 
			boolean[] recStack = new boolean[V]; 
			
			
			// Call the recursive helper function to 
			// detect cycle in different DFS trees 
			for (int i = 0; i < V; i++) 
			if (isCyclicUtil(i, visited, recStack)) 
			return true; 
			
			return false; 
			} 
			static boolean same(int []arr)
			{
				for(int i=1;i<arr.length;i++)
					if(arr[i]!=arr[0]&&arr[0]!=Integer.MAX_VALUE&&arr[i]!=Integer.MAX_VALUE)
						return false;
				return true;
			}
			static int inv(int[] arr)
			{
				int tot=0;
				for(int i=0;i<arr.length;i++)
				{
					for(int j=i+1;j<arr.length;j++)
						if(arr[i]>arr[j])
							tot++;
					
				}
				return tot;
			}
			static boolean ab(int[] a,int[] b,int i,int k,int inv,int[] p)
			{
				if(i==a.length)
				{
					if(inv(b)<=inv)
						return true;
					else
						return false;
				}
				for(int j=k;j>=1;j--)
				{
					int in=a.length-a.length%j-1;
					if(p[in]==0)
					{
						b[i]=j;
						p[in]=j;
						if(ab(a, b, i+1, k, inv, p))
								return true;
					}
					else {
						b[i]=p[in];
					}
					
				}
				return false;
			}
			static int prime(int n)
			{
				for(int i=n;;i++)
				{
					boolean flag=true;
					for(int j=2;j<i;j++)
						if(i%j==0)
						{
							flag=false;
							break;
						}
					if(flag)
						return i;
				}
				
			}
public static void main(String[] args)throws IOException
{
	BufferedReader bReader=new BufferedReader(new InputStreamReader(System.in));
	FastReader fs=new FastReader();
int T=fs.nextInt();
	
	while(T-->0)
	{
		StringBuilder sb=new StringBuilder();
		int n=fs.nextInt();
		if(n==1)
		{
			System.out.println("6");
			continue;
		}
		if(n==2)
		{
			System.out.println("15");
			continue;
		}
		int prev=prime(n+1);
		//System.out.println(prev+","+prime(prev+n));
		long ans=prime(prev+n)*prev;
		
		System.out.println(ans);
	}
	

}
}
