Цікава задача#124

Цікава задача

1 second
512 megabytes
Medium

Арифметична прогресія це послідовність чисел виду

a_1, a_1 + d, a_1 + 2d, \dots, a_1 + (n-1)d, \dots

де a_1 — це перший член прогресії, — це фіксована різниця між попереднім та наступним.

Степан, дізнавшись про проведення ІІІ етапу Всеукраїнської олімпіади з інформатики, вирішив запропонувати учасникам непросту, цікаву задачу, на тему "Арифметична прогресія".

Він бере довільне додатне число і виписує на дошці арифметичну прогресію з першим членом рівним і різницею, рівною також , тобто маємо послідовність A, A+A, A+2A, A+3A, \dots. Степана цікавить перше число в даній послідовності, яке є повним кубом деякого натурального числа. Степан довів, що для любого натурального числа в описаній вище арифметичній прогресії існує повний куб деякого натурального числа.

Наприклад, перший член арифметичної прогресії 2, тоді маємо виписати на дошці послідовність 2, 4, 6, 8, ... Четвертий член цієї арифметичної прогресії є повним кубом числа 2\ (8 = 2^3).

Напишіть програму, яка для заданого числа , визначає мінімальну кількість членів арифметичної прогресії, які потрібно виписати на дошці, щоб серед них був повний куб деякого натурального числа.

Input

Єдиний рядок вхідного файлу містить одне ціле число A\ (1 \leq A \leq 10^9).

Output

Вихідний файл має містити одне ціле число — мінімальну кількість членів арифметичної прогресії, які потрібно виписати на дошці, щоб серед них був повний куб.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

Четвертий член арифметичної прогресії (2, 4, 6, 8, \dots) є повним кубом числа 2\ (8 = 2^3).

Другий член арифметичної прогресії (4, 8, \dots) є повним кубом числа 2\ (8 = 2^3).

Перший член арифметичної прогресії є повним кубом числа 5\ (125 = 5^3).

Scoring

Рішення, які вірно працюють для A \leq 10 набиратимуть не менше 20 балів.