Parking Lot

The parking lot at Hilbert's Mall needs to be infinitely large, since infinitely many shoppers come to shop at its infinitely many shops. Fortunately, you are one of the first people to arrive! Unfortunately, there's rather a lot of competition for parks close to the entrance. The parking lot can be considered a plane, where the entrance to the mall is at point $(0, 0)$, and there is a park at every coordinate $(N, M)$, where $N$ and $M$ are non-negative integers. Note that there is a park at coordinate $(0, 0)$, the same position as the entrance.

Initially, the carpark is empty. Every time a car arrives, it will take the unoccupied park which has the shortest straight-line distance to the entrance, or any one of them if there are several. You are the $P$th person to arrive. How close to the entrance will you park, assuming no car leaves before you arrive?

Input

A single positive integer $P$.

Output

A single positive integer $D$, the square of the straight line distance between the coordinate you park at and the entrance (the squared distance is requested to ensure it is an integer).

Subtasks

• Subtask 1 (25%): $P \le 1,000$.
• Subtask 2 (25%): $P \le 1,000,000$.
• Subtask 3 (50%): $P \le 1,000,000,000$.

Sample Explanations

In the first sample case, you are the first car to arrive. You take the park at $(0, 0)$, and so have a squared distance of $0$ to the entrance.

In the second sample case, you are the ninth car to arrive. You take the park at $(2, 2)$, and so have a squared distance of $2^2+2^2=8$ to the entrance.