Given a integer N. Find number of possible ways to represent N as a sum of at most five cubes.

Input

First line contains N.

1<=N<=125000.

Output

Output the result

Example

Input:
64
Output:
2