require 'prime'
p = Prime.each(1299709).to_a

def bs(n,a)
    mid = a[(a.size)/2]
    if n == mid
        return 0
    elsif a[a.size/2 - 1] < n && n < mid
        return mid - a[a.size/2 - 1]
    elsif n < mid
        bs(n,a[0...(a.size/2)])
    else
        bs(n,a[(a.size/2)...a.size])
    end
end

loop do
    k = gets.to_i
    break if k == 0
    puts bs(k,p)
end