main :: IO()
main = getContents >>= mapM_ (print . solve . read) . lines
    where solve n = length $ takeWhile (<= n) primes

primes :: [Int]
primes = (2 :) . (3 :) . (5 :) . (7 :) $ filter isPrime [11, 13..] 

isPrime :: Int -> Bool
isPrime n
    | n < 2     = False
    | otherwise = n == last (sieveOfE [2..n])
    -- Sieve of Eratosthenes
    where sieveOfE :: [Int] -> [Int]
          sieveOfE []  = []
          sieveOfE [a] = [a]
          sieveOfE all@(x:xs)
              | x < 2           = error "`head list` must be `> 1`"
              | last xs < x ^ 2 = all
              | otherwise       = x : sieveOfE [n | n <- all, n `mod` x /= 0]
