AMR11E  Distinct Primes
Arithmancy is Draco Malfoy's favorite subject, but what spoils it for him is that Hermione Granger is in his class, and she is better than him at it. Prime numbers are of mystical importance in Arithmancy, and Lucky Numbers even more so. Lucky Numbers are those positive integers that have at least three distinct prime factors; 30 and 42 are the first two. Malfoy's teacher has given them a positive integer n, and has asked them to find the nth lucky number. Malfoy would like to beat Hermione at this exercise, so although he is an evil git, please help him, just this once. After all, the knowitall Hermione does need a lesson.
Input
The first line contains the number of test cases T. Each of the next T lines contains one integer n.
Output
Output T lines, containing the corresponding lucky number for that test case.
Constraints
1 <= T <= 20
1 <= n <= 1000
Example
Sample Input: 2 1 2 Sample Output: 30 42
hide comments
Mukund Kumar:
20140208 15:16:16
my 100th problem :) 

Chandan Mittal:
20131121 20:54:35
piece of cake :) 

KARTIK KESHRI:
20130718 09:37:07
got AC in 1st attempt in 0.00s 

BLANKRK:
20130716 16:56:08
nthng spacl... :P 

Vipul Pandey:
20130715 18:41:30
easy one. got ac in 0.00s. there is no need to sort. 

Nishant Gupta:
20130603 15:08:12
brings up my half century \m/ 

Ouditchya Sinha:
20130505 10:07:38
AC in 0.00s :P :) 

Eduardo Nunes:
20130426 20:31:49
easy one, brute force gives AC in 0.01 sec ;)


Aditya Gourav:
20130215 00:00:02
can't believe solved it using brute force,


!!.Nginx.!!:
20130117 14:37:42
getting ans for n=1000 is 2664

Added by:  Varun Jalan 
Date:  20111215 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Varun Jalan  ICPC Asia regionals, Amritapuri 2011 