#include<iostream>
using namespace std;

int main()
{
	const long n=1299710;
	bool a[n];
	int i,j;
	a[1]=0;
	for(i=2;i<n;i++)
		a[i]=1;
	for(i=2;i<n;i++)
		for(j=2;j*i<n;j++)
			a[j*i]=0;
	short b[20];
	short m=0;
	short min,max;
	do{
		cin>>b[m];
		m++;
	}while(b[m-1]!=0);
	for(i=0;i<m-1;i++)
	{
		if(a[b[i]]==1)
			cout<<"0"<<endl;
		else if(a[b[i]]==0)
			{
				min=b[i];
				max=b[i];
				while(a[min]==0)min--;
				while(a[max]==0)max++;
				cout<<max-min<<endl;
			}
	}
	
	return 0;
}