В научно‑исследовательском институте, где работает Тимофей, продолжается успешное исследование ряда натуральных чисел. Каждый день его коллеги открывают всё новые и новые свойства этой последовательности, и Тимофей старается от них не отставать. Сегодня Тимофей, как обычно, выписал на доске в ряд натуральные числа. Потом пришёл начальник отдела и стёр все числа, делящиеся на 2. Потом пришёл начальник другого отдела и стёр все числа из оставшихся, делящиеся на 3. Какое число теперь стоит на n-м месте в списке?
Формат входных данных
Единственная строка входных данных содержит натуральное число nn (1≤n≤109).
Формат выходных данных
Выведите одно натуральное число ответ на вопрос задачи.
Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Система оценки
Решения, верно работающие при 1≤n≤105, получат не менее 40 баллов.
Замечание
В примере дано n=5.
Из исходного ряда натуральных чисел 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, …… сначала были удалены числа 2, 4, 6, 8, …… (как делящиеся на 2).
Остался ряд 1, 3, 5, 7, 9, 11, 13, 15, ……
Потом из него были удалены числа 3, 9, 15, …… (как делящиеся на 3).
Остался ряд 1, 5, 7, 11, 13, ……
На пятом месте число 13.
Ввод
5
Вывод
13