The sequence of n - 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n. For example, (24, 25, 26, 27, 28) between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer k, the length of the prime gap that contains k. For convenience, the length is considered 0 in case no prime gap contains k.



Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or 0 otherwise. No other characters should occur in the output.

Example

Input

10
11
27
2
492170
0


Output

4
0
6
0
114
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;

vector<int> pg(){
  vector<int> pl(1299710,1);
  pl[0]=pl[1]=0;
  for(int i=2;i*i<=1299709;++i)
    if(pl[i])
      for(int j=i*i;j<=1299709;j+=i)
        pl[j]=0;
  int old=2;
  vector<int> v(1299710,0);
  for(int i=3;i<=1299709;++i){
    if(pl[i]){
      int l=i-old;
      for(int j=old+1;j<i;++j){
        v[j]=l;
      }
      old=i;
    }
  }
  return v;
}

int main() {
  vector<int> v=pg();
  while(1){
    int n;
    cin>>n;
    if(!n)break;
    cout<<v[n]<<endl;
  }
  return 0;
}