Задача 89. Твоя невеста ≡

Условие

...

Автомобиль подлетел и зовёт,

И ты выходишь ко мне. Ты похожий на торт.

Такой же белый и красивый, никому не отдам.

И то, что влипла я по пояс, видел и доберман.

Я попробую кусочек и дойдем с тобой до точек, е...

Я буду вместо, вместо, вместо неё

Твоя невеста честно, честная ё.

Я буду вместо, вместо, вместо неё твоя!

...

Максим Фадеев, "Невеста", 2003 г.

Видеоклип

У Натальи — свадебный переполох! Выбор платья, фаты, цветов, ресторана, музыки — всему нужно успеть уделить время! Времени мало, а дел много.

Сегодня невеста выбирает свадебный торт. Конечно, он должен быть красивым, вкусным и, самое главное, — многоэтажным. Согласно представлениям Натальи об идеальном торте, на вершине должен располагаться корж радиуса 1, под ним — корж радиуса a или b, под ним (и каждым следующим) — корж радиусом в a или b раз больше предыдущего. Например, при a = 2 и b = 3 идеальный торт может быть таким: 1-2-6-12-24-... Или таким: 1-3-6-18-36-... Или таким: 1-3-9-27-81-...

Максимальный радиус нижнего коржа торта не может превышать r — в противном случае его невозможно будет вынести из кондитерского цеха. Из всех идеальных тортов невеста предпочтет тот, у которого радиус самого нижнего коржа максимален. Помогите Наталье — посчитайте по известным a, b и r радиус нижнего коржа самого предпочтительного торта.

Формат входных данных

Первая строка входного файла содержит три натуральных числа, записанных через пробел: a, b и r.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу.

Ограничения

2 ≤ a < b < r ≤ 10¹⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере Наталья посчитает идеальными следующие пять тортов:

1-2-4-8.

1-2-4-12.

1-2-6-12.

1-3-6-12.

1-3-9.

Самым предпочтительным для Натальи станет торт, у которого размер нижнего коржа максимален, в нашем случае этот размер равен 12, сразу у трех тортов.

Примеры тестов

2 3 15

12