// 2007アジア地区予選B : Prime Gap

#include <fstream>

using namespace std;

int main(){
	ifstream fin("B.in");
	const int maxP = 1299710;
	bool pr[maxP+1];
	for(int i=2;i<=maxP;i++) pr[i] = true;
	for(int i=2;i<=maxP;i++){
		if(!pr[i]) continue;
		for(int j=2*i;j<=maxP;j+=i)
			pr[j] = false;
	}
	int p;
	while(fin >> p, p){
		int L = p, R = p;
		while(!pr[L]) L--;
		while(!pr[R]) R++;
		printf("%d\n", R-L);
	}
}