#P1420. 素数区间

素数区间

Background

Description

给出整数a,b 和数值k a,b代表[a,b]区间, 求出最小的长度l,使得[a,b]区间内任何一个长度为l的连续区间中素数的数量>=k.

Format

Input

一行包含三个空格分隔的整数a、 b、 k (1 ≤ a,b,k≤ 10 6; a≤b).

Output

在一行中打印单个整数 — 所需的最小l 。如果没有解决方案,请打印 -1。

Samples

2 4 2
3
6 13 1
4
1 4 3
-1

Limitation

1s, 1024KiB for each test case.