#P1725G. Garage

Garage

Description

Pak Chanek plans to build a garage. He wants the garage to consist of a square and a right triangle that are arranged like the following illustration.

Define aa and bb as the lengths of two of the sides in the right triangle as shown in the illustration. An integer xx is suitable if and only if we can construct a garage with assigning positive integer values for the lengths aa and bb (a<ba<b) so that the area of the square at the bottom is exactly xx. As a good friend of Pak Chanek, you are asked to help him find the NN-th smallest suitable number.

The only line contains a single integer NN (1N1091 \leq N \leq 10^9).

An integer that represents the NN-th smallest suitable number.

Input

The only line contains a single integer NN (1N1091 \leq N \leq 10^9).

Output

An integer that represents the NN-th smallest suitable number.

Samples

样例输入 1

3

样例输出 1

7

Note

The 33-rd smallest suitable number is 77. A square area of 77 can be obtained by assigning a=3a=3 and b=4b=4.