#include <bits/stdc++.h>

#define N 1300005
int primes[100005], cnt;
std::bitset<N> isprime;

void check(void) {
    isprime.set();
    isprime[1] = 0;

    for(int i = 2; i <= N; ++ i) {
        if(isprime[i])
            primes[++ cnt] = i;

        for(int j = 1; j <= cnt && i * primes[j] <= N; ++ j) {
            isprime[i * primes[j]] = false;
            if(!(i % primes[j]))
                break;
        }
    }

    return;
}

int main(void) {
    int n, p;

    check();

    while(true) {
        scanf("%d", &n);
        if(!n)
            break;
        
        p = std::lower_bound(primes, primes + N, n) - primes;
        if(primes[p] == n)
            puts("0\n");
        else
            printf("%d\n", primes[p] - primes[p - 1]);
    }
    
    return 0;
}

cnt 很诡异地指到了一个很大的数...