Description

Newman and Bamboo are good friends. One day, Newman taught Bamboo the famous Joseph Problem: there are N persons numbered 1 to N standing round a circle. They stand clockwise according to their numbers (namely 1, 2, 3, 4, …, N). Then, starting from 1, the killer kills every 2nd person he counts until there is only one person left whose number is J(N). We can easily infer that J(1) = 1, J(5) = 3 and J(6) = 5. Bamboo finds this problem intriguing and starts thinking. Suddenly, he finds that if he continually uses J(N) to be the term in J, he can finally get a fixed number. For example, J(2) = 1, so J(J(2)) = 1, J(J(…J(2)…)) = 1. Newman agrees with Bamboo but Bamboo is not satisfied. Furthermore, Bamboo wants to know what the fixed number will be for a specific N. Can you help us?

Input

Only one line containing n (1 ≤ n ≤ 10¹⁰⁰⁰⁰).

Output

Only one line containing K such that J(J(J(J…J(N)…))) = K and J(K)=K.

10

3

Hint

J(10) = 5, J(5) = 3, J(3) = 3.

Source

POJ Monthly--2006.08.27, zcgzcgzcg