/* 14:50-15:03 */
#include <iostream>
#include <vector>

using namespace std;

vector<int> primes;

void sieve()
{
  bool flags[1299710];

  for (int i = 0; i <= 1299709; ++i) { flags[i] = true; }
  flags[0] = flags[1] = false;

  for (int i = 2; i <= 1299709; ++i) {
    if (!flags[i]) { continue; }
    else { primes.push_back(i); }
    for (int j = i*2; j <= 1299709; j += i) {
      flags[j] = false;
    }
  }
}

int main()
{
  int k;
  sieve();
  while (cin >> k) {
    if (k == 0) { break; }
    for (vector<int>::iterator p = primes.begin(); p < primes.end(); ++p) {
      if (k == (*p)) { cout << 0 << endl; break; }
      if (k < (*p)) { cout << (*(p) - *(p-1)) << endl; break; }
    }
  }
  return 0;
}