require 'prime'
def solve(arr, v)
  l = -1
  r = arr.size
  while l + 1 < r
    m = (l + r) / 2
    if arr[m] < v then l = m
    else r = m
    end
  end
  arr[r] - arr[l]
end
primes = Prime.each.take(100000)
while n = gets.to_i
  break if n == 0
  puts Prime.prime?(n) ? 0 : solve(primes, n)
end