/* 
   AOJ 1276
   Prime Gap
   2015/7/23
*/

#include<stdio.h>
#define MAX_PRIME 1500000

void get_prime_list(int* prime_list)
{
  int i, j;

  for(i = 0; i < MAX_PRIME; i++)
    {
      prime_list[i] = 1;
    }

  prime_list[0] = 0;
  prime_list[1] = 0;

  for(i = 0; i < MAX_PRIME; i++)
    {

      if(prime_list[i] == 1)
	{
	  for(j = i; i * j < MAX_PRIME && 0 < i * j; j++)
	    {
	      prime_list[i * j] = 0;
	    }
	}
    }
  
}

int count_length(int* prime_list)
{
  
}

int ans_f(int n, int* prime_list)
{
  int i, u_count = 0, d_count = 0;

  for(i = n; prime_list[i] != 1; i++)
    {
      u_count++;
    }

  for(i = n; prime_list[i] != 1; i--)
    {
      d_count++;
    }

  return u_count + d_count;
}


int main(void)
{
  int n, length, prime_list[MAX_PRIME];

  get_prime_list(prime_list);

  while(1)
    {
      scanf("%d", &n);
      if(n == 0)
	{
	  break;
	}
      length = ans_f(n, prime_list);
      printf("%d\n", length);
    }
  return 0;
}