import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.container;

immutable MAX = 1300000;
bool p[MAX];
int res[MAX];

void main()
{
	
	p[] = 1;
	p[0..2] = 0;
	foreach (i; 2..sqrt(MAX*1.0).ceil.to!int) {
		if (p[i]) {
			foreach (j; iota(i*2, MAX, i))
				p[j] = 0;
		}
	}

	int pre = 3, cnt;
	foreach (i; 4..MAX) {
		if (p[i]) {
			res[pre+1..i] = cnt + 1;
			cnt = 0;
			pre = i;
		} else {
			cnt++;
		}
	}

	while (1) {
		auto x = readln.chomp.to!int;
		if (!x) break;
		res[x].writeln;
	}
}