#include <iostream>
#include <cmath>

using namespace std;

int ifPrime[1299710];

int main()
{
	for ( int i = 0 ; i <= 1299709 ; i ++ )
		ifPrime[i] = true;
	ifPrime[0] = false;
	ifPrime[1] = false;
	for ( int i = 2 ; i <= sqrt((double)1299710) ; i ++ )
	{
		if ( ifPrime[i] )
			for ( int j = 2 ; i * j <= 1299709 ; j ++ )
				ifPrime[i*j] = false;
	}
	int number;
	while ( true )
	{
		cin>>number;
		if ( number == 0 )
			break;
		int left, right;
		for ( int i = number ; i > 1 ; i -- )
		{
			if ( ifPrime[i] )
			{
				left = i;
				break;
			}
		}
		for ( int i = number ; i <= 1299709 ; i ++ )
		{
			if ( ifPrime[i] )
			{
				right = i;
				break;
			}
		}
		cout<<right-left<<endl;
	}
}