#include <iostream>
#include <vector>

using namespace std;

const int N = 1299710;

vector<bool> p;

void init(){
    p.assign(N, true); p[0] = p[1] = false;
    for(int i=2; i<=N; ++i)if(p[i]){
        for(int j=i<<1; j<=N; j+=i)p[j] = false;
    }
}

int main(){
    init();
    for(int k; cin >> k, k;){
        int lo = k, hi = k;
        while(!p[lo])lo--;
        while(!p[hi])hi++;
        cout << hi - lo << '\n';
    }
    return 0;
}