/*
 * Copyright (c) 2007 Kamo Hiroyasu
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * ACM ICPC 2007 Asia Regional Contest, Tokyo
 *  Problem B  Prime Gap
 *   Author: Kamo Hiroyasu <wd@ics.nara-wu.ac.jp>
 */

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define INPUT_LIMIT	1299709

unsigned
floor_sqrt(unsigned x)
{
	unsigned	y, h, a;

	y = 0;
	for (h = 1U << ((sizeof(unsigned) * CHAR_BIT - 1) / 2);
	     h > 0; h /= 2) {
		a = (h + y * 2) * h;
		if (x >= a) {
			x -= a;
			y += h;
		}
	}
	return y;
}

int
isprime(unsigned x)
{
	unsigned	i, i_max;
	int		d;

	switch (x) {
	case 0:
	case 1:
	case 4:
		return 0;
	case 2:
	case 3:
	case 5:
		return 1;
	}
	switch (x % 6) {
	case 0:
	case 2:
	case 3:
	case 4:
		return 0;
	}
	for (i = 5, i_max = floor_sqrt(x), d = 2;
	     i <= i_max; i += d, d = 6 - d) {
		if (x % i == 0)
			return 0;
	}
	return 1;
}

unsigned
prime_gap_length(unsigned x)
{
	unsigned	m, n;

	if (x < 2 || isprime(x))
		return 0;
	m = x + 1;
	while (!isprime(m)) {
		m ++;
	}
	n = x - 1;
	while (!isprime(n)) {
		n --;
	}
	return m - n;
}

int
main(int argc, char *argv[])
{
	const char	*path = "B.in";
	char		*cmd;
	FILE		*fp;
	unsigned	x;

	cmd = argv[0];
	argc --;
	argv ++;
	switch (argc) {
	case 1:
		path = *argv;
	case 0:
		break;
	default:
		fprintf(stderr, "%s: too many arguments\n", cmd);
		exit(1);
	}
	if ((fp = fopen(path, "r")) == NULL) {
		perror(path);
		exit(2);
	}
	while (fscanf(fp, "%u", &x) == 1 && x != 0) {
#ifndef NDEBUG
		if (x <= 1 || x > INPUT_LIMIT) {
			printf("*\n");
			continue;
		}
#endif
		printf("%u\n", prime_gap_length(x));
	}
	return 0;
}