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
pvsmpraveen:
20160131 17:00:16
Easy one !! Sieve() Pre() O(1) 0.00 :) 

azam_9:
20160129 14:29:39
simple bruite force..nothing else..:P 

uzumaki_75:
20160116 18:41:22
AC in one go :) 

vaibhavi760:
20160108 21:53:50
sieve .... easy problem AC in one go 

Junaid:
20151227 17:21:01
And with this problem completed my half century on SPOJ....:P 

skrishna99:
20151113 14:28:46
I just added primes up to 500 in an array , used a loop and checked if the number is divided by at least 3 primes . It took 1 full day for me. 

jack_jay:
20151028 13:37:18
easier1.........use sieve. 

SangKuan:
20150707 03:45:03
for who's answer for n = 1000 is 2988,there is at least three distinct prime factors,it is mean equal or bigger than three 

Dushyant Singh:
20150605 19:10:00
Got it. :) I was calculating for 3 distinct prime factors only i.e. not for number of distinct prime factors greater than 3. 

Ankush :
20150605 08:55:01
Simple Brute Force and, used cin and cout. AC in 0.00 :P 
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 