#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x) {
	if (x == 2) return true;
	for (int i=2; i*i <= x; ++i) if (x % i == 0) return false;
	return true;
}

int main() {
	int k;
	while (cin >> k, k != 0) {
		if (isPrime(k)) puts("0");
		else {
			int ans = 1, x = k-1;
			while (!isPrime(x)) {
				++ans;
				--x;
			}
			
			x = k+1;
			while (!isPrime(x)) {
				++ans;
				++x;
			}
			
			cout << ans + 1 << endl;
		}
	}
}
