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

import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main{

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;
	int[] ps = new int[100000];
	void prime() {
		boolean[] p = new boolean[1500000];
		int index = 0;
		for(int i=2;i<=1299709;i++)if(!p[i]) {
			ps[index++] = i;
			for(int j=i*2;j<=1299709;j+=i) p[j] = true;
		}
	}
	
	int binSearch(int x) {
		int l = 0, r = 100000;
		for(;l < r;) {
			int c = (l+r) / 2;
			if(x == ps[c]) return c;
			else if( x < ps[c] ) r = c;
			else if( x > ps[c] ) l = c+1;
		}
		return l;
	}
	
	void run() {
		Scanner sc = new Scanner(System.in);
		prime();
		for(;;) {
			int n = sc.nextInt();
			if(n == 0) break;
			int id = binSearch(n);
			if(ps[id] == n) System.out.println(0);
			else System.out.println(ps[id] - ps[id-1]);
		}
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}