require 'prime'
h = Hash.new(0)
max = 1
prev = 0
ret = 0
while n = gets.to_i do
    b = false
    h.each_key do |k|
        if n < k
            puts h[k]-1
            b = true
            break
        end
    end
    next if b
    Prime.each do |p|
        next if p <= max
        h[p] = h[prev] + 1
        ret = h[prev]
        prev = p
        max = p
        break if p > n
    end
    puts ret
end