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 n-th 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 know-it-all 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
Eduardo Nunes: 2013-04-26 20:31:49

easy one, brute force gives AC in 0.01 sec ;-)
just find lucky numbers up to 2664, sort, and print :-D

Aditya Gourav: 2013-02-15 00:00:02

can't believe solved it using brute force,
got AC in 0.02 sec :D

!!.Nginx.!!: 2013-01-17 14:37:42

getting ans for n=1000 is 2664
then also WA... :(

Paul Draper: 2012-12-27 17:00:03

Recommend increasing maximum size of n.

eliminator: 2012-10-27 10:24:49

2664=(2^3)*(3^2)*(37) is a 1000th lucky no. ... ;)

ken_taiken: 2012-07-31 02:02:30

@Shizuo Heiwajima : The constraints are correct.

*tazo*: 2012-04-12 15:24:56

2664 is a lucky number, 2^3*3^2*37 2,3 and 37 are prime numbers, but I am getting runtime error is there a bigger number in the test case?

numerix: 2012-03-24 20:57:56

@santosh kumar: Read comments to a problem before writing your own ...

(^_^): 2012-03-24 20:33:12

please give me the answer for n=1000
I am getting 3224 is this correct??
I am getting WA for this.

Thanks numerix got AC for 1000 answer is 2664

Last edit: 2012-03-27 06:54:51
rajni: 2012-02-25 06:36:44

@summit jha 2664=2^3*3*37*3


Added by:Varun Jalan
Date:2011-12-15
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