// Aizu 1276: Prime Gap
// 2017.9.21 bal4u@uu

#include <stdio.h>
#include <ctype.h>

#define MAX  1299709
#define SQRT 1140     // sqrt(MAX)
char prime[MAX + 5], *pmax = prime + MAX;

void mkprime()
{
	int k;
	register char *p, *q;
	prime[1] = 0, prime[2] = 0;
	for (p = prime + 4; p <= pmax; p += 2) *p = 1;
	for (k = 3, p = prime + 3; k <= SQRT; k += 2, p += 2)
		if (!*p) for (q = p + k; q <= pmax; q += k) *q = 1;
}

int main()
{
	int n, ans;

	mkprime();
	while (scanf("%d", &n) && n) {
		ans = 0;
		if (prime[n]) {
			ans = n + 1;
			while (prime[--n]);
			while (prime[ans]) ans++;
			ans -= n;
		}
		printf("%d\n", ans);
	}
	return 0;
}