Sieve of Eratosthenes is an algorithm for making tables of primes. In this algorithm we sequentially write down the integers from 2 to the highest number n we wish to include in the table. Cross out all numbers >2 which are divisible by 2 (every second number). Find the smallest remaining number >2. It is 3. So cross out all numbers >3 which are divisible by 3 (every third number). Find the smallest remaining number >3. It is 5. So cross out all numbers >5 which are divisible by 5 (every fifth number) and so on. At the end of this algorithm, all unmarked numbers are prime numbers.
Now, I observed that only first 4 prime no. are needed to find all prime no less than 100 (120 to be exact). This makes me wonder, if I choose only first N prime no. for my sieve generation then what will be the upper limit of my table, i.e. first composite no which will be identified as prime no if we use only first N prime no. for sieve generation.
First line will contain no. of test cases T.
T lines follow. Each line will contain only one integer N
Output first composite no which will be identified as prime no, if we use only first N prime no. for sieve generation, for each test case on separate lines.
T <= 70001
N <= 70000 (First 70000 prime no are < 10^6)
Problem Setter : Pushkar Anand