Given an integer n, find the smallest integer x that satisfies two conditions:

• x is greater than or equal to n;
• There is a pair of non-negative integers (a, b) such that x = a3 + a2 * b + a * b2 + b3.

Input

One nonnegative integer n (n ≤ 1018).

Output

Print the smallest value of x.