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 = ka + kb + kc (k > 0).

Help Ibrahim to solve this problem.

Input

One integer n (4 ≤ n ≤ 1018).

Output

Print one integer - the amount of different fours of numbers.