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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
typedef pair<int,int> P;

//-----------------------------------------------------------------------

const int SZ=1300000;
bool isPrime[SZ];

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    for(int i=2;i<SZ;i++) isPrime[i]=true;
    for(int i=2;i<SZ;i++){
        if(!isPrime[i]) continue;
        for(int j=2*i;j<SZ;j+=i) isPrime[j]=false;
    }
    
    int n;
    while(cin>>n,n)
    {
        int p1=n,p2=n;
        while(!isPrime[p1]) p1++;
        while(!isPrime[p2]) p2--;
        cout<<p1-p2<<endl;
    }

}

