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
/*
文字列の配列の初期化、整数の型がlongになっているか
関数（splitとかcontainsとか）内では"+"とかは正規表現となされるので"\\+"とする
配列のコピーはarr1=arr.clone()
HashSet<>[]はおのおの初期化した？？？？？
 */
import java.util.*;
import java.awt.*;
import java.awt.geom.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        int[] prime=Generate_prime(1299709);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) break;
            int d = Arrays.binarySearch(prime, n);
            if (n == 1 || d > 0) {
                out.println(0);
            } else {
                d = ~d;
                out.println(prime[d] - prime[d - 1]);
            }
        }
    }
    static int[] Generate_prime(int n) {
        ArrayList<Integer> prime = new ArrayList<>();
        prime.add(2);
        prime.add(3);
        for (int i = 6; i <= n; i += 6) {
            int p1 = i - 1, p2 = i + 1;
            if (isPrime(p1)) prime.add(p1);
            if (isPrime(p2)) prime.add(p2);
        }
        int t=prime.size();
        int[] Generated_prime=new int[t+1];
        //Iteratorでもよい
        for (int i=1;i<=t;i++){
            Generated_prime[i]=prime.get(i-1);
        }
        return Generated_prime;
    }
    static boolean isPrime(int p){
        if(p==1)return false;
        int t= (int) (sqrt(p)+1);
        boolean f=true;
        for (int i = 5; i <= t && f; i++) if(p%i==0) f=false;
        return f;
    }
}
