#include <stdio.h>
#define N_MAX 1299709

char isprime[N_MAX + 1];

int main(void)
{
    int i, j;

    /* sieve */
    for(i = 1; i <= N_MAX; i++)
        isprime[i] = 1;
    for(i = 2; i <= N_MAX; i++)
        if(isprime[i])
            for(j = 2 * i; j <= N_MAX; j += i)
                isprime[j] = 0;

    while(scanf("%d", &i), i)
    {
        if(isprime[i])
            printf("%d\n", 0);
        else
        {
            int count = 2;
            for(j = i + 1; j <= N_MAX && !isprime[j]; j++)
                count++;
            for(j = i - 1; j <= N_MAX && !isprime[j]; j--)
                count++;
            printf("%d\n", count);
        }
    }

    return 0;
}