Ни для кого не секрет, что сейчас Уилл Тёрнер — капитан Летучего Голландца. В далёком A-м году ему пришлось заключить договор с богиней Калипсо, согласно которому Уилл немедленно отправился в вечное плавание и сможет сойти на берег только через B лет после отплытия. Более того, договор не позволяет Уиллу более дня находиться на суше — он обязан будет вновь пуститься в плавание на очередные B лет.

Сегодняшний день очень важен для Уилла, ведь это очередная годовщина начала его плавания. С момента заключения договора он ещё ни разу не выходил на сушу. Чтобы немного развлечь себя, каждый год в этот самый день Уилл, отрываясь от своих многочисленных забот, выделяет k минут на кажущееся бесполезным со стороны занятие — проверку того, является ли номер текущего года простым числом. Но Уилл видит в этом особый смысл — по легенде, в конце года с простым номером богиня Калипсо может отменить один из заключённых ранее с ней договоров. Капитан Летучего Голландца умеет проверять число на простоту лишь одним способом: последовательно делить его на все натуральные числа подряд, начиная с двойки и заканчивая числом, на единицу меньшим проверяемого. Поскольку Уилл не силён в математике и что-либо считает лишь раз в год, то для того, чтобы разделить одно число на другое, ему требуется целая минута. Если за k минут делитель номера года не найден, то Уилл бросает подсчёты и считает его простым. А в конце такого года он тешит себя надеждами, что именно сейчас богиня Калипсо явится к нему с радостными вестями. Так сколько же всего лет будут простыми по мнению Уилла в период с первой годовщины отплытия и до года, когда он в первый раз сможет выйти на берег, включительно, если богиня не сжалится над пиратом?

В единственной строке через пробел записаны целые числа A, B и k (2 ≤ A, B ≤ 10⁹; 1 ≤ k ≤ 300).

Выведите единственное целое число — количество лет в указанном периоде, имеющих простой номер, по мнению Уилла.

Уилл посчитает года 25 и 29 простыми, а 24, 26, 27, 28 и 30 — нет.