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
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        prime = self.sieve(1299709)
        while True:
            n = input()
            if n == 0:
                break
            if prime[n]:
                print 0
            else:
                lower = upper = n
                while not prime[lower]:
                    lower -= 1
                while not prime[upper]:
                    upper += 1
                print upper - lower
        
        return None

    def sieve(self, n):
        f = [True for i in xrange(n+1)]
        f[0] = False
        f[1] = False
        i = 2
        while i * i <= n:
            if f[i]:
                j = 2
                while i * j <= n:
                    f[i * j] = False
                    j += 1
            i += 1
        return f


if __name__ == '__main__':
    m = Main()
    m.solve()