#include <bits/stdc++.h>

using namespace std;

#define MAX 1299710
#define SQRTMAX 1141

bool prime[1299709];

int main()
{
    prime[0] = prime[1] = false;
    fill(prime+2, prime+MAX, true);
    for(int p=2; p<SQRTMAX; p++)
    {
        if(prime[p])
        {
            for(int i=2*p; i<MAX; i+=p)
            {
                prime[i] = false;
            }
        }
    }

    int n;
    while(cin >> n, n)
    {
        if(prime[n])
        {
            cout << 0 << endl;
        }
        else
        {
            int f = n;
            int t = n;
            while(!prime[f]) f--;
            while(!prime[t]) t++;
            cout << t - f << endl;
        }

    }
}