## Algorithm

C. Primes on Interval
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You've decided to carry out a survey in the theory of prime numbers. Let us remind you that a prime number is a positive integer that has exactly two distinct positive integer divisors.

Consider positive integers aa + 1...b (a ≤ b). You want to find the minimum integer l (1 ≤ l ≤ b - a + 1) such that for any integer x (a ≤ x ≤ b - l + 1) among l integers xx + 1...x + l - 1 there are at least k prime numbers.

Find and print the required minimum l. If no value l meets the described limitations, print -1.

Input

A single line contains three space-separated integers a, b, k (1 ≤ a, b, k ≤ 106a ≤ b).

Output

In a single line print a single integer — the required minimum l. If there's no solution, print -1.

Examples
input
Copy
`2 4 2`
output
Copy
`3`
input
Copy
`6 13 1`
output
Copy
`4`
input
Copy
`1 4 3`
output
Copy
`-1`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <stdio.h>

using namespace std;

int const N = 1e6 + 1;
int a, b, k, cs[N];
bool prime[N];

void sieve() {
memset(prime, true, sizeof prime);
prime[0] = prime[1] = false;

for(int i = 2; i * i < N; ++i)
if(prime[i])
for(int j = i * i; j < N; j += i)
prime[j] = false;

cs[0] = 0;
for(int i = 1; i <= N; ++i)
cs[i] = cs[i - 1] + prime[i - 1];
}

bool can(int mid) {
for(int i = a; i <= b - mid + 1; ++i)
if(cs[i + mid] - cs[i] < k)
return false;
return true;
}

int main() {
sieve();

scanf("%d %d %d", &a, &b, &k);

int l = 1, r = b - a + 1, mid, res = -1;
while(l <= r) {
mid = (l + r) >> 1;
if(can(mid)) {
r = mid - 1;
res = mid;
} else
l = mid + 1;
}

printf("%d\n", res);

return 0;
}``````
Copy The Code &

Input

cmd
2 4 2

Output

cmd
3