Скалозуб Балди собрал N послов иностранных держав для разъяснения им своей политики и рассадил их за круглым столом. Места за столом пронумерованы натуральными числами от 1 до N по часовой стрелке.
Когда Скалозуб Балди в своей речи сказал лишнего в первый раз, заседание покинул посол, сидевший за первым местом. Когда Скалозуб сказал лишнего во второй раз, заседание покинул посол, сидевший через одного посла от уже покинувшего заседание. Далее, всегда, когда Скалозуб Балди говорит лишнего в очередной раз, заседание покидает посол, сидевший через одного посла по часовой стрелке от посла, покинувшего заседание перед ним. Какое место за столом останется занятым после того, как Скалозуб Балди погорячится и сморозит что-то не то в (N-1)-й раз?

Входные данные.
Строка содержащая значение N - натуральное число, не превосходящее одного миллиарда.

Выходные данные.
Одно натуральное число - номер места, за которым сидит последний оставшийся посол.

Пример.

на входе:
10

на выходе:
4

Примечание. Послы уходят в таком порядке: 1, 3, 5, 7, 9, 2, 6, 10, 8.