#include <cstdio>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int c=1300000;
bool prime[c+1];
vector<int> pr;
void makeprime(){
	rep(i,c+1) prime[i]=1;
	prime[0]=0,prime[1]=0;
	for(int i=2;i+i<=c;i++) if(prime[i]) for(int j=2;j*i<=c;j++) prime[i*j]=0;
	rep(i,c+1) if(prime[i]) pr.push_back(i);
}
int main(){
	makeprime();
	while(true){
		int n;
		scanf("%d",&n);
		if(!n) break;
		if(prime[n]){
			printf("0\n");
			continue;
		}
		printf("%d\n",pr[upper_bound(pr.begin(),pr.end(),n)-pr.begin()]-pr[upper_bound(pr.begin(),pr.end(),n)-pr.begin()-1]);
	}
}