Background

石老板觉得老是抽奖不够刺激，所以这次开始抢

Description

定义f(x)是x的最小质因子。例如f(8) = f(10) = 2，f(9) = 3。 求出x在[s, e]范围内的，最小的前k个质因子的和。 2 <= s <= 1e18，s+100 <= e <= s+1e6，1 <= k <= 0.9*(e-s+1)。 现在，支持人给出三个数s、e和k，谁能最快的准确回答这个问题，就能上台领取一份奖品。

Format

Input

三个数，s、e和k。

Output

前k个最小质因子的和。

Samples

100 200 70

165

Limitation

1s, 1024KiB for each test case.