import           Control.Applicative
import           Control.Monad
import           Data.List           hiding (union)
import           Text.Printf

main :: IO ()
main = mapM_ (print . process . read) . lines =<< getContents
  where
    process n = length $ takeWhile (<=n) primesPQWE

---------------------------------------------------------------------------
primesTME :: [Int]
primesTME = 2 : ([3,5..] `minus` foldt [[p*p,p*p+2*p..] | p <- primes_])
   where
     primes_ = 3 : ([5,7..] `minus` foldt [[p*p,p*p+2*p..] | p <- primes_])
     foldt ((x:xs):t)    = x : union xs (foldt (pairs t))
     pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t               -- (* Treefold Merge Eratosthenes *)
----------------------------------------------------------------------------
primesTMWE :: [Int]
primesTMWE = 2:3:5:7: gaps 11 wheel (fold3t $ roll 11 wheel primes_)
  where
   primes_ = 11: gaps 13 (tail wheel) (fold3t $ roll 11 wheel primes_)     -- separate feed
   fold3t ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)
                                      `union` fold3t (pairs t)              -- fold3t: 5% ~ 10% speedup
   pairs ((x:xs):ys:t)         = (x : union xs ys) : pairs t
   wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
           4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
   gaps k ws@(w:t) cs@ ~(c:u) | k==c  = gaps (k+w) t u              -- (*  better fold, w/ Wheel!   *)
                              | True  = k : gaps (k+w) t cs
   roll k ws@(w:t) ps@ ~(p:u) | k==p  = scanl (\c d->c+p*d) (p*p) ws
                                          : roll (k+w) t u
                              | True  = roll (k+w) t ps
----------------------------------------------------------------------------
minus :: [Int] -> [Int] -> [Int]
minus xs@(x:xt) ys@(y:yt) = case compare x y of
  LT -> x : minus xt ys
  EQ ->     minus xt yt
  GT ->     minus xs yt
minus a         b         = a

union :: [Int] -> [Int] -> [Int]
union xs@(x:xt) ys@(y:yt) = case compare x y of
  LT -> x : union xt ys
  EQ -> x : union xt yt
  GT -> y : union xs yt
union a         []        = a
union []        b         = b

--------------------------------------------------------------------------------
primesPQWE::[Int]
primesPQWE = 2 : 3 : 5 : 7 : sieve 11 wheel
  where
    -- Here we use a wheel to generate all the number that are not multiples
    -- of 2, 3, 5, and 7.  We use some hard-coded data for that.
    wheel :: Integral a => [a]
    wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:4:8:6:4:6:2:4:6
      :2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel

    -- This version of the sieve takes a wheel, not a list to be sieved.
    -- primes1 and primes2 represent the same infinite list of, but they are
    -- consumed at different speeds.  By creating separate expressions, we
    -- avoid retaining all the material between the two points.  Sometimes
    -- (when you care about space usage) memoization is not your friend.

    sieve :: Integral a => a -> [a] -> [a]
    sieve n [] = []
    sieve n wheel@(d:ds) = n : (map (\(p,wheel) -> p) primes1) where
      primes1 = sieve' (n+d) ds initialTable
      primes2 = sieve' (n+d) ds initialTable
      initialTable = initHQ (insertPQ (n*n) (n, wheel) emptyPQ)
                   (map (\(p,wheel) -> (p*p,(p,wheel))) primes2)
    sieve' n []     table = []
    sieve' n wheel@(d:ds) table
        | nextComposite <= n = sieve' (n+d) ds (adjust table)
        | otherwise	     = (n,wheel) : sieve' (n+d) ds table
        where
            nextComposite = minKeyHQ table
            adjust table
                | m <= n    = adjust (deleteMinAndInsertHQ m' (p, ds) table)
                | otherwise = table
                where
		              (m, (p, d:ds)) = minKeyValueHQ table
		              m' = m + p * d

-- Priority Queues;  this is essentially a copy-and-paste-job of
-- PriorityQ.hs.  By putting the code here, we allow the Haskell
-- compiler to do some whole-program optimization.  (Based on ML
-- code by L. Paulson in _ML for the Working Programmer_.)

data PriorityQ k v = Lf
                   | Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k v)
               deriving (Eq, Ord, Read, Show)

emptyPQ :: PriorityQ k v
emptyPQ = Lf

isEmptyPQ :: PriorityQ k v -> Bool
isEmptyPQ Lf = True
isEmptyPQ _  = False

minKeyValuePQ :: PriorityQ k v -> (k, v)
minKeyValuePQ (Br k v _ _) = (k,v)
minKeyValuePQ _            = error "Empty heap!"

minKeyPQ :: PriorityQ k v -> k
minKeyPQ (Br k v _ _) = k
minKeyPQ _            = error "Empty heap!"

minValuePQ :: PriorityQ k v -> v
minValuePQ (Br k v _ _) = v
minValuePQ _            = error "Empty heap!"

insertPQ :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v
insertPQ wk wv (Br vk vv t1 t2)
               | wk <= vk   = Br wk wv (insertPQ vk vv t2) t1
               | otherwise  = Br vk vv (insertPQ wk wv t2) t1
insertPQ wk wv Lf             = Br wk wv Lf Lf

siftdown :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v -> PriorityQ k v
siftdown wk wv Lf _             = Br wk wv Lf Lf
siftdown wk wv (t @ (Br vk vv _ _)) Lf
    | wk <= vk                  = Br wk wv t Lf
    | otherwise                 = Br vk vv (Br wk wv Lf Lf) Lf
siftdown wk wv (t1 @ (Br vk1 vv1 p1 q1)) (t2 @ (Br vk2 vv2 p2 q2))
    | wk <= vk1 && wk <= vk2    = Br wk wv t1 t2
    | vk1 <= vk2                = Br vk1 vv1 (siftdown wk wv p1 q1) t2
    | otherwise                 = Br vk2 vv2 t1 (siftdown wk wv p2 q2)

deleteMinAndInsertPQ :: Ord k => k -> v -> PriorityQ k v -> PriorityQ k v
deleteMinAndInsertPQ wk wv Lf             = error "Empty PriorityQ"
deleteMinAndInsertPQ wk wv (Br _ _ t1 t2) = siftdown wk wv t1 t2

leftrem :: PriorityQ k v -> (k, v, PriorityQ k v)
leftrem (Br vk vv Lf Lf) = (vk, vv, Lf)
leftrem (Br vk vv t1 t2) = (wk, wv, Br vk vv t t2) where
    (wk, wv, t) = leftrem t1
leftrem _                = error "Empty heap!"

deleteMinPQ :: Ord k => PriorityQ k v -> PriorityQ k v
deleteMinPQ (Br vk vv Lf _) = Lf
deleteMinPQ (Br vk vv t1 t2) = siftdown wk wv t2 t where
    (wk,wv,t) = leftrem t1
deleteMinPQ _ = error "Empty heap!"

-- A hybrid of Priority Queues and regular queues.  It allows a priority
-- queue to have a feeder queue, filled with items that come in an
-- increasing order.  By keeping the feed for the queue separate, we
-- avoid needlessly filling an O(log n) data structure with data that
-- it won't need for a long time.

type HybridQ k v = (PriorityQ k v, [(k,v)])

initHQ :: PriorityQ k v -> [(k,v)] -> HybridQ k v
initHQ pq feeder = (pq, feeder)

insertHQ :: (Ord k) => k -> v -> HybridQ k v -> HybridQ k v
insertHQ k v (pq, q) = (insertPQ k v pq, q)

deleteMinAndInsertHQ :: (Ord k) => k -> v -> HybridQ k v -> HybridQ k v
deleteMinAndInsertHQ k v (pq, q) = postRemoveHQ(deleteMinAndInsertPQ k v pq, q)
    where
        postRemoveHQ mq@(pq, []) = mq
        postRemoveHQ mq@(pq, (qk,qv) : qs)
            | qk < minKeyPQ pq = (insertPQ qk qv pq, qs)
            | otherwise        = mq

minKeyHQ      :: HybridQ k v -> k
minKeyHQ (pq, q) = minKeyPQ pq

minKeyValueHQ :: HybridQ k v -> (k, v)
minKeyValueHQ (pq, q) = minKeyValuePQ pq



Measured memory_bytes: 16472