#include<iostream>
#include<cmath>
using namespace std;
#define MAX 1299709

int main()
{	
	int i,j,n;
	char prime[MAX+1];

	memset(prime,1,(MAX+1));
	prime[1]=0;
	for(i=2;i<=(int)sqrt((double)MAX);i++)
	{
		if(prime[i])
		{
			j=i*2;
			while(j<=MAX)
			{
				prime[j]=0;
				j+=i;
			}
		}
	}
	while(cin>>n)
	{
		if(n==0)	break;
		i=n;
		while(!prime[i])	--i;
		j=n;
		while(!prime[j])	++j;
		cout<<j-i<<endl;
	}
	return 0;
}