eolymp
bolt
Try our new interface for solving problems
Problems

Universal numbers

Universal numbers

Time limit 2 seconds
Memory limit 256 MiB

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.

Input data

One integer n (4n10^18).

Output data

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

Examples

Input example #1
4

Output example #1
3

Input example #2
5

Output example #2
6

Input example #3
10

Output example #3
9


Author Rashad Mammadov
Source 2019 Azərbaycan National İnformatiks Olimpiad, Final, May 5