#include<stdio.h>
int prime[1300001];

void isprime(void){
    int i,j,n,c;

    for(i = 4;i<1300001;i += 2)prime[i] = 1;

    for (i = 3;i * i <= 1300001;i += 2){
        if (prime[i] == 0){
            for (j = i + i; j <= 1300001; j += i){
                prime[j] = 1;
            }
        }
    }
}

int main(void){
    int n,i,a;
     
    isprime();
    
    while (scanf("%d",&n),n){
        a = 0;
        for (i = n; prime[i]; i++)a++;
        for (i = n; prime[i]; i--)a++;
        printf("%d\n", a);
    }
     
    return (0);
}