import Data.Array (listArray, (!), bounds)

main = ps `seq` main'
    where
    ps = primesUnder 1000000
    main' = interact (unlines . map step . lines)
    step = show . count ps . read 

primesUnder m = ps `seq` listArray (1, length ps) ps
    where
    ps = siege [2..m]
    siege (p:xs)
        | p*p > m = p:xs
        | otherwise = p:siege [x|x<-xs, x `mod` p /= 0]

count ps x = count' a b
    where
    (a,b) = bounds ps
    count' a b
        | x == ps!m = m
        | x < ps!m = if a == m then m-1 else count' a (m-1)
        | x > ps!m = if b == m then m+1 else count' (m+1) b
        where m = (a+b) `div` 2