Secret Committee members, Little Petar and Little Tux, enjoy playing the board game "Kule" during the breaks between preparing contests and exam revision. The rules of the game assume that the players initially have at their disposal a set of cubes, stacked together to form a tower.

A single turn has Petar splitting the tower into two or more smaller towers, and then ordering these smaller towers in an array. Tux then has to choose one of the smaller towers. This tower will be used for all future turns, while the remainder is discarded. If Tux chooses the kth tower, Petar is obliged to pay k² dinars to him immediately (e.g. if Tux chose the 3rd tower in the array, Petar has to give him 9 dinars). The game concludes when only a single cube remains.

As it is well-known that Secret Committee members don't have time for anything (including playing games), Petar and Tux decided to, instead of actually playing the game, trust each other that they would have played optimally, and that Petar should immediately give Tux the amount of dinars that he would have won under that condition. They have asked for your help in determining this amount.

Input

The first and only line of the standard input contains a single integer N, the number of cubes in the initial tower.

Output

Write to the first and only line of the standard output a single integer M, representing the amount of dinars that Petar should give to Tux.

Example

Input:
7

Output:
8

Explanation

In one of the possible pair of optimal strategies for Petar and Tux, Petar first splits the tower into two towers of heights 5 and 2 (in that order). Tux chooses the second tower and he immediately gets 4 dinars, after which Petar is forced to split the tower into two towers of heights 1 each. Tux once again chooses the second tower, gaining a total of 8 dinars.

Constraints

• 2 <= N <= 10¹⁰⁰