Ibrahim loves to play with numbers. He recently learned how to raise numbers to a power, and he really likes it. Farhad knows this, so he asked Ibrahim the following question: in how many different ways can one represent n as the sum of three numbers with the same integer non-negative base k raised to a non-negative integer.
In other words, you must find the number of different fours of non-negative integers (k, a, b, c), satisfying the equality n = k^a
+ k^b
+ k^c
(k > 0).
Help Ibrahim to solve this problem.
One integer n (4 ≤ n ≤ 10^18
).
Print one integer - the amount of different fours of numbers.