SPOJ.com - Problem DCEPC505

DCEPC505 - Bazinga!

no tags

Sheldon is very proud of his intelligence. To test his intelligence Howard designs a puzzle and asks him to solve it. The puzzle consists of special numbers which can be obtained by multiplying exactly two distinct prime numbers. Sheldon has to tell Howard what is the Kth element of this series. Help him.

For Example 6, 10, 14, 15 are the first few members of this series whereas 4, 9 and 12 are not.

Input

First line specifies T, the number of test cases.

Next T lines each gives 1 number, K

Output

Output 1 line for each test case giving the Kth element of this series.

Constraints

1 <= T <= 1000

1 <= K <= 2000000

Example

Input:
4
2
3
5
7

Output:
10
14
21
26

Submit solution!

hide comments

< Previous 1 2 3 Next >

	ngoc_ty: 2024-06-20 23:03:07 the bound of products is 10527449 and bound of primes is 5263697.
	magnesium12: 2023-06-08 14:38:13 More refined N = 10527450, although this would hardly make any difference. Last edit: 2023-06-08 14:39:07
	ayu_031201: 2022-01-09 13:01:40 N= 10600000 . and check if d is prime and n/d should also be a prime where d\|n. Last edit: 2022-01-09 13:06:40
	dhruv788: 2020-07-14 11:22:49 Just solved it after a hell lot of work, Try using sieve with linear complexity
	ni_kill12: 2019-10-08 18:14:38 what could be for k=6 and tell me how ? plis and also how 26 for k=7 ??? Last edit: 2019-10-08 18:15:54
	y17prashant: 2019-01-08 21:10:14 just take care of size while implementing seive costed me overflow and RTE
	sphere913: 2018-10-22 16:56:48 how to find bounds? hint please
	nadstratosfer: 2018-06-30 11:44:35 Francky, your 0.00s here is such an eyesore ;) Can it be reproduced or is it a result of some server instability? Started solving this in C just to downvote for all the frustration I've had trying to pass with Python several months back. Turned out the TL is not that bad: my best solution is 9x times faster than my first AC one. Spent some time cutting the fat off my program and enjoyed it. Apparently PyPy can get AC too! Thanks to the setter for not making it easy. =(Francky)=> It's not instability, ;-) At time I've solved it Python was not available, but now yes ! I'll try to find my old files... My C code is quite unreadable. [NG]: It's wizardry then. Chapeau bas! =(Francky)=> J'ai vu nombreux de tes jolis scores, j'en profite pour te féliciter également ;-) Last edit: 2018-07-01 15:48:33
	Ricardo Bittencourt: 2015-02-11 14:00:41 Please add Haskell.
	Bharath Reddy: 2014-09-28 15:42:27 Phew! Took 6 hours to get AC, after 3 TLEs. Had to write a separate brute force program just to find the bounds. Time limit is too strict. Had to several optimizations in sieve implementation.

Submit solution!

Added by:	dce coders
Date:	2012-04-18
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	Own Problem