#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>

using namespace std;

const int MAX = 1299710;
bool prime[MAX];
vector<int> V;

void make(){
  fill(prime,prime+MAX, 1);
  prime[0] = prime[1] = 0;
  for(int i = 2; i < sqrt(MAX); i++)
    if(prime[i]) for(int j = 2*i; j < MAX; j+=i) prime[j] = 0;

  for(int i = 2; i < MAX; i++) 
    if(prime[i]) V.push_back(i);
}
int main(){
  make();
  vector<int>::iterator ite;
  int in;
  while(cin >> in && in){
    ite = upper_bound(V.begin(),V.end(),in);
    if(!prime[in])cout << *ite-*(ite-1) << endl;
    else cout << "0" << endl;
  }
  return 0;
}