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

hide comments
m2do: 2018-03-19 13:13:16

simple_sieve <3

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.

Rishav Goyal: 2014-06-10 23:49:14

i can't beliveve ac after so many tle :D :D:

Mostafa 36a2: 2014-02-13 21:56:13

OverFlow :)

anurag garg: 2014-01-06 20:56:51

took 3 hours to determine the bounds and 1 hour to remove Sigsegv error...finally AC

Sir_Ostara: 2014-01-05 08:01:47

NZEC in Java for Test Case 5..pls hlp :(

napster: 2013-02-22 09:58:54

getting runtime error after running 5 test cases .......my submission id:8761900

S__L: 2013-01-20 08:34:32

Check for the bounds ! ;)

Avinash Thummala: 2013-01-05 23:12:07

Nice prob!


Added by:dce coders
Date:2012-04-18
Time limit:0.422s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C CPP C++ 4.3.2 CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem