require "prime"
primes = []
Prime.each(1299709){|prime| primes << prime}
arr = [nil, nil, 0]
primes.each_cons(2){|prime1, prime2|
    arr[prime2] = 0
    (prime1 + 1).upto(prime2 - 1){|i| arr[i] = prime2 - prime1}
}
while true
    x = gets.to_i
    break if x == 0
    puts arr[x]
end
