1644

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

int n;
int arr[1300000];
vector<int> v;

int main()
{
	int lo,hi,mid;
	for(int i=0;i<1300000;i++)
	{
		arr[i]=0;
	}

	for(int i=2;i<sqrt(1300000);i++)
	{
		if(arr[i]==0)
		{
			for(int j=i+i;j<1300000;j+=i)
			{
				arr[j]=1;
			}
		}
	}

	for(int i=2;i<1300000;i++)
	{
		if(arr[i]==0)
		{
			v.push_back(i);
		}
	}
	//cout<<v.size()<<"\n";
	while(scanf("%d",&n),n)
	{
		if(arr[n]==0)
		{
			cout<<0<<"\n";
			continue;
		}
		lo=0;hi=v.size()-1;
		while(hi-lo>1)
		{
			if((hi-lo)%2)
			{
				mid=lo+(hi-lo)/2+1;
			}
			else
				mid=lo+(hi-lo)/2;
			//cout<<lo<<" "<<mid<<" "<<hi<<" "<<n<<"\n";
			//getchar();
			if(n<v[mid])
			{
				hi=mid;
			}
			else
			{
				lo=mid;
			}
		}
		cout<<v[hi]-v[lo]<<"\n";
	}
	return 0;
}