#include<iostream>
#include <cstring>
using namespace std;
const int N = 25600000;
bool a[N];
int p[N];
int n;
void Prime() 
{
	memset(a, 0, n*sizeof(a[0]));
	int num = 0, i, j;
	for(i = 2; i < n; ++i) 
	{
		if(!(a[i])) p[num++] = i;
		for(j = 0; (j<num && i*p[j]<n); ++j) 
		{
			a[i*p[j]] = 1;
			if(!(i%p[j])) break;
		}
	}
	a[0]=true,a[1]=true;
}
int main()
{
	n=1299710;
	Prime();
	int number;
	while(cin>>number && number)
	{
		int i,j;
		for(i=number;i>=2;--i)
		{
			if(a[i])continue;
			break;
		}
		for(j=number;j<=1299709;++j)
		{
			if(a[j])continue;
			break;
		}
		cout<<j-i<<endl;
	}
	return 0;
}