#include <stdio.h>

static int p[ 1299710 ] = { 1, 1, 0 };
static int q[ 1299710 ] = { 1, 1, 0 };

/** Application main entry point. */
int
main (
  int     argc,
  char  * argv[ ]
  )
{
  int i, j;

  for ( i = 2; i * i <= 1299709; ++i )
  {
    if ( p[ i ] ) continue ;

    for ( j = i * i; j <= 1299709; j += i )
    {
      p[ j ] = 1;
    }
  }
  for ( i = 1299709; i >= 2; --i )
  {
    q[ i ] = !!( p[ i ] )
           ? q[ i + 1 ]
           : i;
  }
  for ( i = 2; i <= 1299709; ++i )
  {
    p[ i ] = !!( p[ i ] )
           ? p[ i - 1 ]
           : i;
  }

  for ( ; ; )
  {
    int n;

    scanf ( "%d", &n );
    if ( !( n ) ) break ;

    printf ( "%d\n", q[ n ] - p[ n ] );
  }

  return ( 0 );
}