#include<stdio.h>

int judge(int);

int main()
{
  int i,j,n;
  while(1){
    scanf("%d",&n);
    if(n==0)break;
    for(i=n,j=0;i<=1299709;i++,j++){
      if(judge(i)==1)break;
    }
    for(i=n;i>0;i--,j++){
      if(judge(i)==1)break;
    }   
    printf("%d\n",j);
  }
  return 0;
}

int judge(int n){
  int i;
  if(n<2)return 0;
  if(n==2)return 1;
  if(n%2==0)return 0;
  for(i=3;i<n;i+=2){
    if(n%i==0)return 0;
  }
  return 1;
}