ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2012

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Not So Simple Years

Time limit: 1.0 second
Memory limit: 64 MB
Bootstrap: Aye, Captain Turner. This ship has a purpose again. And where we are bound, she cannot come. One day ashore, ten years at sea. That's a steep price for what's been done.
Will: Depends on the one day.
It's an open secret that Will Turner is the captain of the Flying Dutchman. In a distant year A he was forced to sign a contract with the goddess Calypso, according to which Will had to go into endless sailing and he could come ashore only B years after leaving. Moreover, the agreement allows Will to spend only one day on land, and after that he must resume sailing for another B years.
Today is an anniversary of his departure since the formation of the contract, that’s why this day is very important for Will. Since then he has never come out on the land. To amuse himself a little, every year on this special day Will allocates k minutes to check whether the number of the current year is a prime number, which seems a nail biting from the side. But for Will there is a special meaning in this action, because, according to the legend, at the end of the year, which number is prime, goddess Calypso can cancel one of the previously concluded treaties. Captain of the Flying Dutchman know only one way to check the number’s primality. He consequently divide it by all the natural numbers in a row, starting with 2 and ending with a number, one less than verifiable. As Will not good at math, and he count anything only once a year, dividing one number by another takes him a minute. If after k minutes divider of the number of the year is not found, Will stops counting and considers it prime. At the end of such year he consoles himself with hope that here and now the goddess Calypso will come to him with the good news. So how many years are prime, according to Will, in the period from the first anniversary of departure to the year, when he for the first time will be able to get to shore inclusive, if goddess won’t take pity on the pirate?

Input

The only line contains space separated integers A, B and k (2 ≤ A, B ≤ 109; 1 ≤ k ≤ 300).

Output

Output an amount of years which numbers Will considers prime.

Sample

inputoutput
23 7 3
2

Notes

Will will consider numbers 25 and 29 to be prime but won't consider numbers 24, 26, 27, 28, and 30.
Problem Author: Ksenia Karpova (prepared by Egor Shchelkonogov)
Problem Source: Open Ural FU Championship 2012
To submit the solution for this problem go to the Problem set: 1940. Not So Simple Years