#include <stdio.h>
int prime[1299710];
void SetPrime(int max){
    int i,o;
    for(i=4;i<=max;i+=2)
        prime[i]=1;
    for(i=3;i*i<=max;i+=2){
        if(prime[i]==0)
            for(o=i*2;o<=max;o+=i)
                prime[o]=1;
    }
}
int main(void){
    int num,sum,i;
    SetPrime(1299709);
    prime[0]=prime[1]=1;
    for(;scanf("%d",&num),num;){
        if(!prime[num])
            printf("0\n");
        else{
            for(sum=0,i=num;prime[i];i++,sum++);
            for(i=num-1;prime[i];i--,sum++);
            printf("%d\n",sum+1);
        }
    }
    return 0;
}