URI Online Judge | 2589

The Biggest Prime Gap

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

Prime gap ​​refers to the difference between consecutive prime numbers. For example, the distance between prime ​​7 and 11 is 4, just as the distance between prime ​​23 and 29 is 6. The challenge is, given a number, considering all previous and the number itself, what is the largest distance between Consecutive prime numbers?

Write a program that, given a number, computes the biggest prime gap.

Input

There will be several test cases. Each test case will have an integer N (2 ≤ N ≤ 109). The entry ends with end of file.

Output

For each test case, print the largest distance between consecutive cousins, from 1 to N.

Input Sample Output Sample

10
11
12
30

2
4
4
6