Kth Losing Position in the Box Game

There are \(n\) boxes, and initially each box contains exactly one chess piece. Two players take turns making moves. In each move, a player selects a box \(i\) that currently contains a piece and a positive integer \(p\), and then moves the piece from box \(i\) to box \(2^p\times i\). If the destination box already contains a piece, then both pieces are removed from that box. A player who cannot make a move loses the game.

It can be proved that, when both players play optimally, the outcome (win or loss for the first player) depends only on \(n\). We call the position a losing position (i.e. a winning position for the second player) if the first player cannot force a win.

Your task is: Given an integer \(k\), determine the \(k\)th smallest \(n\) such that the initial configuration (with boxes \(1,2,\ldots,n\) each holding one piece) is a losing position for the first player (i.e. the second player can force a win).

Note: In the initial position every valid move will remove two pieces. It turns out that the losing positions occur in an arithmetic progression. After careful analysis one may show that the \(k\)th losing position is given by

[ n = 5k - 4. ]

Given \(k\), output \(n = 5k - 4\>.

inputFormat

The input consists of a single line containing one integer \(k\) (\(1 \le k \le 10^9\)).

You may assume that the answer \(n\) fits in a 64-bit signed integer.

outputFormat

Output a single integer: the \(k\)th smallest \(n\) such that the second player wins the game.

sample

1

1