M = 1299710

isPrime = [1]*M

isPrime[0],isPrime[1] = 0,0

lp = [0]*M; p = []

b = 2

for i in range(2,M):

    if isPrime[i]:

        for j in range(i*i,M,i):

            isPrime[j] = 0

        p.append(i)

        b = i

    lp[i] = b

while 1:

    n = eval(input())

    if n==0: break

    print(p[p.index(lp[n])+1]-lp[n] if lp[n]!=n else "0")

    
M = 1299710

isPrime = [1]*M

isPrime[0],isPrime[1] = 0,0

for i in range(2,M):

    if isPrime[i]:

        for j in range(i*i,M,i):

            isPrime[j] = 0

while 1:

    n = eval(input())

    if n==0: break

    p = q = n

    if isPrime[n]:

        print(0)

    else:

        while isPrime[p]==0:p-=1

        while isPrime[q]==0:q+=1

        print(q-p)

    
M = 1299710
isPrime = [1] * M
isPrime[0], isPrime[1] = 0, 0
lp = [0] * M
p = []
b = 2
for i in range(2, M):
    if isPrime[i]:
        for j in range(i * i, M, i):
            isPrime[j] = 0
        p.append(i)
        b = i
    lp[i] = b
while 1:
    n = eval(input())
    if n == 0:
        break
    print(p[p.index(lp[n]) + 1] - lp[n] if lp[n] != n else "0")

M = 1299710
isPrime = [1] * M
isPrime[0], isPrime[1] = 0, 0
for i in range(2, M):
    if isPrime[i]:
        for j in range(i * i, M, i):
            isPrime[j] = 0
while 1:
    n = eval(input())
    if n == 0:
        break
    p = q = n
    if isPrime[n]:
        print(0)
    else:
        while isPrime[p] == 0:
            p -= 1
        while isPrime[q] == 0:
            q += 1
        print(q - p)

-lp = [0] * M -p = [] -b = 2 -        p.append(i) -        b = i -    lp[i] = b -    print(p[p.index(lp[n]) + 1] - lp[n] if lp[n] != n else "0") +    p = q = n +    if isPrime[n]: +        print(0) +    else: +        while isPrime[p] == 0: +            p -= 1 +        while isPrime[q] == 0: +            q += 1 +        print(q - p)