#include <stdio.h>
#define N 1300000
int p[N+1];
void era(void){
	int i,j;
	for(i=2;i<=N;i++){
		p[i]=1;
	}
	for(i=2;i*i<=N;i++){
		if(p[i]){
			for(j=i+i;j<=N;j+=i){
				p[j]=0;
			}
		}
	}
}
int main(void){
	int n,k,i;
	era();
	while(1){
		scanf("%d",&n);
		if(!n){
			break;
		}
		k=0;
		for(i=n;p[i]==0;i++){
			k++;
		}
		for(i=n;p[i]==0;i--){
			k++;
		}
		printf("%d\n",k);
	}
	return 0;
}