{-# OPTIONS_GHC -O2 #-}
 
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Data.Char
 
 
main = do
  s <- getContents
  forM_ (takeWhile (isDigit . head) $ words s) $ \w-> do
    -- let ps = primesTo (read w)
    -- print (length ps, last ps)        -- leaks badly
    print (lastPrimes (read w))          -- no leak
 
sieveUA :: Int -> UArray Int Bool
sieveUA top = runSTUArray $ do
    let m = (top-1) `div` 2
        r = floor . sqrt . fromIntegral $ top + 1 
    sieve <- newArray (1,m) True                 -- :: ST s (STUArray s Int Bool)
    forM_ [1..r `div` 2] $ \i -> do
      isPrime <- readArray sieve i
      when isPrime $                             -- ((2*i+1)^2-1)`div`2 = 2*i*(i+1)
        forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> 
          writeArray sieve j False
    return sieve
 
primesTo :: Int -> [Int]
primesTo top = 2 : [i*2+1 | (i,True) <- assocs $ sieveUA top]
 
lastPrimes :: Int -> (Int,[Int])   -- (nth, vals)
lastPrimes top = 
  let arr   = sieveUA top
      (b,t) = bounds arr
  in 
     ( 1 + length [() | (i,True) <- assocs arr]
     , (if (top < 13) then (2:) else id) 
        $ reverse $ take 5 [ 2*i+1 | i <- [t,t-1..b], arr ! i ] )
 
{-
ST Array [Int] ON ODDS 
    -= n =-    -= top =- 
    30,000:     350,377:  0.01s  3.7MB
   100,000:   1,299,709:  0.03s  3.7MB
   300,000:   4,256,233:  0.10s  3.7MB
  1 mln -->  15,485,863:  0.43s  4.8MB        time   space (s_0=3.7)
  2 mln -->  32,452,843:  0.98s  5.8MB
  4 mln -->  67,867,967:  2.31s  8.9MB  1m-> n^1.21  n^1.12
  5 mln -->  86,028,121:  3.04s  9.9MB
  6 mln --> 104,395,301:  3.77s 10.9MB   (leak: was: ***6.7s-227MB***!!!) ****
6,500,000-> 113,648,393:  4.14s 10.9MB
  7 mln --> 122,949,823:  4.52s 11.9MB
7,538,613-> 133,000,999:  4.95s 11.9MB
  8 mln --> 141,650,939:  5.32s 13.0MB  4m-> n^1.20  n^0.84
  9 mln --> 160,481,183:  6.12s 14.0MB
 10 mln --> 179,424,673:  6.91s 15.0MB
 15 mln --> 275,604,541: 11.01s 21.1MB
 18 mln --> 334,214,459: 13.65s 24.2MB  8m-> n^1.16  n^0.97 (1m->n^1.01)
 20 mln --> 373,587,883:    TIMEOUT   
-}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KCmltcG9ydCBDb250cm9sLk1vbmFkCmltcG9ydCBDb250cm9sLk1vbmFkLlNUCmltcG9ydCBEYXRhLkFycmF5LlNUCmltcG9ydCBEYXRhLkFycmF5LlVuYm94ZWQKaW1wb3J0IERhdGEuQ2hhcgoKIAptYWluID0gZG8KICBzIDwtIGdldENvbnRlbnRzCiAgZm9yTV8gKHRha2VXaGlsZSAoaXNEaWdpdCAuIGhlYWQpICQgd29yZHMgcykgJCBcdy0+IGRvCiAgICAtLSBsZXQgcHMgPSBwcmltZXNUbyAocmVhZCB3KQogICAgLS0gcHJpbnQgKGxlbmd0aCBwcywgbGFzdCBwcykgICAgICAgIC0tIGxlYWtzIGJhZGx5CiAgICBwcmludCAobGFzdFByaW1lcyAocmVhZCB3KSkgICAgICAgICAgLS0gbm8gbGVhawogCnNpZXZlVUEgOjogSW50IC0+IFVBcnJheSBJbnQgQm9vbApzaWV2ZVVBIHRvcCA9IHJ1blNUVUFycmF5ICQgZG8KICAgIGxldCBtID0gKHRvcC0xKSBgZGl2YCAyCiAgICAgICAgciA9IGZsb29yIC4gc3FydCAuIGZyb21JbnRlZ3JhbCAkIHRvcCArIDEgCiAgICBzaWV2ZSA8LSBuZXdBcnJheSAoMSxtKSBUcnVlICAgICAgICAgICAgICAgICAtLSA6OiBTVCBzIChTVFVBcnJheSBzIEludCBCb29sKQogICAgZm9yTV8gWzEuLnIgYGRpdmAgMl0gJCBcaSAtPiBkbwogICAgICBpc1ByaW1lIDwtIHJlYWRBcnJheSBzaWV2ZSBpCiAgICAgIHdoZW4gaXNQcmltZSAkICAgICAgICAgICAgICAgICAgICAgICAgICAgICAtLSAoKDIqaSsxKV4yLTEpYGRpdmAyID0gMippKihpKzEpCiAgICAgICAgZm9yTV8gWzIqaSooaSsxKSwgMippKihpKzIpKzEuLm1dICQgXGogLT4gCiAgICAgICAgICB3cml0ZUFycmF5IHNpZXZlIGogRmFsc2UKICAgIHJldHVybiBzaWV2ZQogCnByaW1lc1RvIDo6IEludCAtPiBbSW50XQpwcmltZXNUbyB0b3AgPSAyIDogW2kqMisxIHwgKGksVHJ1ZSkgPC0gYXNzb2NzICQgc2lldmVVQSB0b3BdCiAKbGFzdFByaW1lcyA6OiBJbnQgLT4gKEludCxbSW50XSkgICAtLSAobnRoLCB2YWxzKQpsYXN0UHJpbWVzIHRvcCA9IAogIGxldCBhcnIgICA9IHNpZXZlVUEgdG9wCiAgICAgIChiLHQpID0gYm91bmRzIGFycgogIGluIAogICAgICggMSArIGxlbmd0aCBbKCkgfCAoaSxUcnVlKSA8LSBhc3NvY3MgYXJyXQogICAgICwgKGlmICh0b3AgPCAxMykgdGhlbiAoMjopIGVsc2UgaWQpIAogICAgICAgICQgcmV2ZXJzZSAkIHRha2UgNSBbIDIqaSsxIHwgaSA8LSBbdCx0LTEuLmJdLCBhcnIgISBpIF0gKQogCnstClNUIEFycmF5IFtJbnRdIE9OIE9ERFMgCiAgICAtPSBuID0tICAgIC09IHRvcCA9LSAKICAgIDMwLDAwMDogICAgIDM1MCwzNzc6ICAwLjAxcyAgMy43TUIKICAgMTAwLDAwMDogICAxLDI5OSw3MDk6ICAwLjAzcyAgMy43TUIKICAgMzAwLDAwMDogICA0LDI1NiwyMzM6ICAwLjEwcyAgMy43TUIKICAxIG1sbiAtLT4gIDE1LDQ4NSw4NjM6ICAwLjQzcyAgNC44TUIgICAgICAgIHRpbWUgICBzcGFjZSAoc18wPTMuNykKICAyIG1sbiAtLT4gIDMyLDQ1Miw4NDM6ICAwLjk4cyAgNS44TUIKICA0IG1sbiAtLT4gIDY3LDg2Nyw5Njc6ICAyLjMxcyAgOC45TUIgIDFtLT4gbl4xLjIxICBuXjEuMTIKICA1IG1sbiAtLT4gIDg2LDAyOCwxMjE6ICAzLjA0cyAgOS45TUIKICA2IG1sbiAtLT4gMTA0LDM5NSwzMDE6ICAzLjc3cyAxMC45TUIgICAobGVhazogd2FzOiAqKio2LjdzLTIyN01CKioqISEhKSAqKioqCjYsNTAwLDAwMC0+IDExMyw2NDgsMzkzOiAgNC4xNHMgMTAuOU1CCiAgNyBtbG4gLS0+IDEyMiw5NDksODIzOiAgNC41MnMgMTEuOU1CCjcsNTM4LDYxMy0+IDEzMywwMDAsOTk5OiAgNC45NXMgMTEuOU1CCiAgOCBtbG4gLS0+IDE0MSw2NTAsOTM5OiAgNS4zMnMgMTMuME1CICA0bS0+IG5eMS4yMCAgbl4wLjg0CiAgOSBtbG4gLS0+IDE2MCw0ODEsMTgzOiAgNi4xMnMgMTQuME1CCiAxMCBtbG4gLS0+IDE3OSw0MjQsNjczOiAgNi45MXMgMTUuME1CCiAxNSBtbG4gLS0+IDI3NSw2MDQsNTQxOiAxMS4wMXMgMjEuMU1CCiAxOCBtbG4gLS0+IDMzNCwyMTQsNDU5OiAxMy42NXMgMjQuMk1CICA4bS0+IG5eMS4xNiAgbl4wLjk3ICgxbS0+bl4xLjAxKQogMjAgbWxuIC0tPiAzNzMsNTg3LDg4MzogICAgVElNRU9VVCAgIAotfQ==

MTAKMzM0MjE0NDU5Ci0tLQoxMDQzOTUzMDUKLS0tCjIwMTgtMDYtMTUgcmVydW4gZm9yIGN1cnJlbnQgdGltaW5nCjYgbWxuIHByaW1lcywgbGltaXQgMTA0Mzk1MzAxLCB3YXMgMi43OHMgYXQgMjAxMy0wOC0xMgogICAgICAgICBub3cgaXQncyAgICAyLjYzcy0xME1CLCAoIGZhcG9iLCBDKysgOiAwLjI3cy04LjlNQiAsIDkuN3ggZmFzdGVyICkKICAgICAgICAgc28sIG5vIHN1YnN0YW50aWFsIGNoYW5nZQoxOCBtbG4gdG8gMzM0MjE0NDU5LCA5LjY5cy0yNE1CICAoIGZhcG9iLCBDKysgOiAxLjExcy0yMi45TUIgLCA4Ljd4IGZhc3RlciApCiAgbiAgICAgICAgICAgICAgICAgICBuIF4gMS4xOSAg

10
334214459
---
104395305
---
2018-06-15 rerun for current timing
6 mln primes, limit 104395301, was 2.78s at 2013-08-12
         now it's    2.63s-10MB, ( fapob, C++ : 0.27s-8.9MB , 9.7x faster )
         so, no substantial change
18 mln to 334214459, 9.69s-24MB  ( fapob, C++ : 1.11s-22.9MB , 8.7x faster )
  n                   n ^ 1.19