Board game

Yura and Roma enjoy playing various board games together. Recently, the company HAL released a new board game called "Atoms." The rules are as follows: The game set includes a small number of atoms (approximately (10^100)). At the start of the game, a multi-sided die is rolled, with each face showing a natural number from (1) to (2 $\cdot$ 10^9). Once the die shows the number (N), the game board is set up by creating (N) piles of atoms, where the (i)-th pile contains exactly (i) atoms.

During the game, Yura and Roma take turns. On each turn, a player can remove any positive number of atoms from any non-empty pile. The player who cannot make a move loses the game.

Yura enjoys discovering interesting facts about the game "Atoms." Today, he was curious about the question: "How many different first moves can be made?". Roma quickly answered, but then Yura posed another question: "How many first moves can be made such that, with optimal play by the opponent, you can still win?". This second question puzzled them, and they decided to stop playing and start writing an exhaustive search...

Input

The first line of input contains a single positive integer (N) ((1 $\le$ N $\le$ 2 $\cdot$ 10^9)), which is the number that appeared on the die at the start of the game.

Output

Output two integers on a single line, separated by a space - the answers to Yura's first and second questions.

Examples